Pointers để giải quyết nhiệm vụ lập trình động đầy thử thách này

Question

Tôi đã bị mắc kẹt trên một vấn đề trong các PEG Thẩm phán Online, gọi Dominos, mà bạn có thể tìm thấy ở đây:

http://wcipeg.com/problem/domino

tóm lược Mô tả:

Chúng tôi được cung cấp một danh sách các dominos với chiều cao và địa điểm khác nhau, được bố trí theo chiều ngang. Một domino tại vị trí x với chiều cao h, một khi được đẩy sang bên phải, sẽ gõ tất cả các domino tại các vị trí x + 1, x + 2, ..., x + h ngay lập tức. Ngược lại, cùng một domino được đẩy sang bên trái sẽ đánh bật tất cả các domino tại các vị trí x-1, x-2, ..., x-h sang trái.

Số lần đẩy tối thiểu chúng ta có thể làm để lật đổ tất cả các yếu tố thống trị là gì?

Ví dụ:

   | 
    |   | 
| | | | | | 
1 2 3 4 5 6 7 8 

trả lời là . Đẩy domino tại vị trí 1 ngay, domino ở vị trí 8 sang trái.

ràng buộc:

Các đầu vào bắt đầu với một số nguyên duy nhất N ≤ 100.000, số lượng domino, tiếp theo là N cặp số nguyên. Mỗi cặp số nguyên thể hiện vị trí và chiều cao của một domino. (1 ≤ vị trí ≤ 1.000.000.000, 1 ≤ chiều cao ≤ 1.000.000.000) Không có hai domino ở cùng một vị trí.

Memory Giới hạn: 64mb

Thời hạn: 1.00s

LƯU Ý: 60% dữ liệu thử nghiệm có N ≤ 5000.

Có một giải pháp brute-force mà giải quyết vấn đề chỉ cho 60% đầu vào.

Dường như cần có giải pháp tuyến tính phụ hoặc thậm chí tuyến tính sử dụng lập trình động để có được AC cho kích thước đầu vào lớn nhất.

Mọi gợi ý sẽ được đánh giá cao.

Có một gợi ý từ tác giả, mà tôi có thể không hoàn toàn hiểu, trong trường hợp nó là hữu ích:

Thực hiện một hàm đệ quy f (n) cung cấp cho tối thiểu # di chuyển cần thiết để lật đổ n domino đầu tiên.

Bây giờ, làm thế nào để bạn liên hệ f (n) với các giá trị trước đó của f? Domino #n có hai lựa chọn : chuyển sang trái (trong trường hợp này nó lật đổ các domino khác) hoặc đi ngay (trong trường hợp một domino khác nằm bên trái của nó lật đổ nó). Hãy thử làm việc từ đó.

Cảm ơn!

Answer 1

Dưới đây là một giải pháp O(N log N):

1. Hãy tìm hiểu làm thế nào để tính toán ứng domino tận cùng bên trái rơi nếu chúng ta đẩy i-th domino sang bên trái là những gì (hãy biểu thị là như L[i]). Ý tưởng đầu tiên đến với tâm trí của một người là chạy mô phỏng đơn giản. Nhưng đó sẽ là cách quá chậm. Tôi tuyên bố rằng chúng tôi chỉ có thể duy trì một chồng các chỉ số domino "thú vị" khi chúng tôi lặp lại từ trái sang phải. Mã giả cho nó trông giống như sau:

   s = Empty stack of dominos 
   for i = 0 .. n - 1 
       while we can knock s.top() domino by pushing the i-th to the left 
        s.pop() 
       the s.top() is the rightmost domino we cannot hit 
       (if s is empty, we can hit all of them) 
       s.push(i-th domino) 
   

   Mã này chạy theo thời gian tuyến tính (mỗi lần được đẩy một lần và xuất hiện một lần). Nó có vẻ không trực quan lắm (tôi sẽ không viết một bằng chứng chính thức đầy đủ ở đây vì nó sẽ quá dài), nhưng làm việc thông qua các ví dụ nhỏ bằng tay có thể giúp hiểu tại sao nó là chính xác.
   Trong thực tế, kỹ thuật này rất đáng hiểu vì nó thường được sử dụng trong lập trình cạnh tranh (khi một cái gì đó di chuyển từ phải sang trái và chúng ta cần tìm phần tử ngoài cùng bên trái thỏa mãn một số điều kiện cho mỗi phần tử bên phải.).

2. Chúng tôi có thể tính toán R[i] (khoảng cách chúng ta có thể đi nếu chúng ta đẩy i-th domino sang bên phải) theo thời gian tuyến tính theo cách tương tự.

3. Bây giờ chúng tôi biết điều gì sẽ xảy ra nếu chúng tôi chọn đẩy bất kỳ domino nào theo bất kỳ hướng nào. Mát mẻ!

4. Hãy sử dụng lập trình động để tính toán câu trả lời. Hãy để f(i) là số lượng hành động tối thiểu mà chúng tôi cần thực hiện để tất cả các domino lên đến i-th bị loại bỏ hoàn toàn và phần còn lại vẫn bị ảnh hưởng. Quá trình chuyển đổi khá tự nhiên: chúng tôi hoặc đẩy domino sang trái hoặc sang phải. Trong trường hợp trước chúng tôi thực hiện chuyển đổi f(j) + 1 -> f(i), trong đó L[i] - 1 <= j < i. Trong trường hợp thứ hai, quá trình chuyển đổi là f(i - 1) + 1 -> f(R[i]). Giải pháp này là chính xác bởi vì nó cố gắng tất cả các hành động có thể cho mỗi domino.

5. Làm thế nào để làm cho phần này hiệu quả? Chúng tôi cần hỗ trợ hai hoạt động: cập nhật một giá trị trong một điểm và nhận được tối thiểu trong một phạm vi. Cây phân đoạn có thể xử lý chúng trong O(log N). Nó cung cấp cho chúng tôi một giải pháp O(N log N).

Nếu giải pháp này dường như quá khó khăn, trước tiên bạn có thể thử và triển khai một đơn giản hơn: chỉ cần chạy mô phỏng để tính toán L[i] và R[i] và sau đó tính toán mảng lập trình năng động theo định nghĩa (mà không có một cây phân khúc) để hiểu rõ những điều này có ý nghĩa gì trong vấn đề này (nó sẽ nhận được 60 điểm). Khi bạn đã hoàn tất việc đó, bạn có thể áp dụng ngăn xếp và tối ưu hóa phân khúc cây để có được giải pháp đầy đủ.

Trong trường hợp một số chi tiết không rõ ràng, tôi cung cấp một thực hiện một giải pháp đúng đắn để bạn có thể tìm họ ở đó:

#include <bits/stdc++.h> 

using namespace std; 

typedef pair<int, int> pii; 

vector<int> calcLeft(const vector<pii>& xs) { 
    int n = xs.size(); 
    vector<int> res(n, 1); 
    vector<int> prev; 
    for (int i = 0; i < xs.size(); i++) { 
     while (prev.size() > 0 && xs[prev.back()].first >= xs[i].first - xs[i].second) 
      prev.pop_back(); 
     if (prev.size() > 0) 
      res[i] = prev.back() + 2;   
     prev.push_back(i); 
    } 
    return res; 
} 

vector<int> calcRight(vector<pii> xs) { 
    int n = xs.size(); 
    for (int i = 0; i < xs.size(); i++) 
     xs[i].first = -xs[i].first; 
    reverse(xs.begin(), xs.end()); 
    vector<int> l = calcLeft(xs); 
    reverse(l.begin(), l.end()); 
    for (int i = 0; i < l.size(); i++) 
     l[i] = n + 1 - l[i]; 
    return l; 
} 

const int INF = (int) 1e9; 

struct Tree { 

    vector<int> t; 
    int size; 

    Tree(int size): size(size) { 
     t.assign(4 * size + 10, INF); 
    } 

    void put(int i, int tl, int tr, int pos, int val) { 
     t[i] = min(t[i], val); 
     if (tl == tr) 
      return; 
     int m = (tl + tr)/2; 
     if (pos <= m) 
      put(2 * i + 1, tl, m, pos, val); 
     else 
      put(2 * i + 2, m + 1, tr, pos, val); 
    } 

    void put(int pos, int val) { 
     put(0, 0, size - 1, pos, val); 
    } 

    int get(int i, int tl, int tr, int l, int r) { 
     if (l == tl && r == tr) 
      return t[i]; 
     int m = (tl + tr)/2; 
     int minL = INF; 
     int minR = INF; 
     if (l <= m) 
      minL = get(2 * i + 1, tl, m, l, min(r, m)); 
     if (r > m) 
      minR = get(2 * i + 2, m + 1, tr, max(m + 1, l), r); 
     return min(minL, minR); 
    } 

    int get(int l, int r) { 
     return get(0, 0, size - 1, l, r); 
    } 
}; 

int getCover(vector<int> l, vector<int> r) { 
    int n = l.size(); 
    Tree tree(n + 1); 
    tree.put(0, 0); 
    for (int i = 0; i < n; i++) { 
     int x = i + 1; 
     int low = l[i]; 
     int high = r[i]; 
     int cur = tree.get(x - 1, x - 1); 
     int newVal = tree.get(low - 1, x - 1); 
     tree.put(x, newVal + 1); 
     tree.put(high, cur + 1); 
    } 
    return tree.get(n, n); 
} 


int main() { 
    ios_base::sync_with_stdio(0); 
    int n; 
    cin >> n; 
    vector<pii> xs(n); 
    for (int i = 0; i < n; i++) 
     cin >> xs[i].first >> xs[i].second; 
    sort(xs.begin(), xs.end()); 
    vector<int> l = calcLeft(xs); 
    vector<int> r = calcRight(xs); 
    cout << getCover(l, r) << endl; 
    return 0; 
} 

Answer 2

bạn sẽ tạo một mảng 2D trong đó mỗi tế bào chứa một cặp (L, R), biểu thị domino giảm các vị trí cụ thể

Initial Chức biểu thị là Push (trái, phải) bởi Mỗi Domino:

1  2  3  4  5  6  7  8 
<0, 2> <1, 1> <2, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> 

Với điều đó bạn không thể giảm thiểu mảng bằng cách thực hiện một bước di chuyển làm giảm mảng của bạn thành các cặp < 0, 0>. Trong trường hợp này di chuyển từ 1 tới R, từ 3 đến L hoặc 8 đến L.

Đối 1 tới R New Array:

1  2  3  4  5  6  7  8 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> 

Chúng tôi đã chỉ có 1 Move trái, để 8 đến L, do đó New Array:

1  2  3  4  5  6  7  8 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> 

cho chúng ta một mảng 2D của:

1  2  3  4  5  6  7  8 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> // initial 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> // pushed 1 to R 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> // pushed 8 to L 

Vì tất cả các tế bào hiện nay < 0, 0>, chúng tôi chắc chắn rằng al l domino rơi và không ai ở lại.

Answer 3

Vấn đề này có thể được giải quyết trong thời gian O (N) mà không segtree

Như kraskevich đã đề cập, chúng tôi cần tìm mức tối thiểu trong phạm vi từ L[i] - 1 đến i - 1. chúng tôi có thể giữ một danh sách các vị trí thú vị và giá trị dp của nó, trong đó cả hai vị trí và giá trị dp là theo thứ tự tăng dần.

Khi chúng tôi muốn truy vấn tối thiểu từ phạm vi, chúng tôi có thể dễ dàng quét danh sách từ phía sau và tìm điểm thú vị nhỏ nhất nằm trong phạm vi.

Sau khi cập nhật dp[x], chúng tôi sẽ bật lại tất cả các điểm trong danh sách có giá trị dp lớn hơn dp[x] (vì chúng không còn thú vị nữa) và thêm (x, dp[x]) vào danh sách dưới dạng điểm thú vị mới.

Điều này chạy theo thời gian tuyến tính.

int getCover(vector<int> l, vector<int> r) { 
    int n = l.size(); 
    vector<int> dp(n + 1, INF); 
    dp[0] = 0; 
    vector<pii> st; 
    st.emplace_back(0, 0); 
    for (int i = 0; i < n; i++) { 
     int x = i + 1; 
     int low = l[i]; 
     int high = r[i]; 
     int cur = dp[i]; 
     while (st.size() > 1) { 
      pii second_last = st[st.size() - 2]; 
      // if the 2nd last point is within range 
      // then the last point will no longer be interesting 
      if (second_last.first >= low - 1) { 
       // remove the last point 
       st.pop_back(); 
      } else { 
       // the 2nd last point is out of range 
       break; 
      } 
     } 
     dp[x] = min(st.back().second + 1, dp[x]); 
     // continue to pop all the points that are no longer interesting. 
     while (!st.empty() && st.back().second >= dp[x]) { 
      st.pop_back(); 
     } 
     // insert new interesting point 
     st.emplace_back(x, dp[x]); 
     dp[high] = min(dp[high], cur + 1); 
    } 
    return dp[n]; 
}