指針爲解決這一具有挑戰性的動態規劃任務

Question

我一直停留在該PEG在線法官一個問題，所謂的多米諾，你可以在這裏找到：

http://wcipeg.com/problem/domino

摘編說明：

我們給出了不同高度和位置的多米諾骨牌列表，水平排列。 x位置的高度爲h的多米諾骨牌，一旦向右推，將會在x + 1，x + 2，...，x + h位置向右敲擊所有多米諾骨牌。相反，向左推動的同一個多米諾骨牌會將位置x-1，x-2，...，x-h中的所有多米諾骨牌向左擊。

我們可以做什麼來推翻所有多米諾骨牌的最小數量是多少？

實施例：

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

回答是。將位置1的多米諾骨牌向右推，位置8的多米諾骨牌向左。

限制條件：

輸入開始與一個整數N≤100,000，的 骨牌的數量，隨後加入N對的整數。每對整數 代表多米諾骨牌的位置和高度。 （1≤地點≤ 1,000,000,000，1≤高度≤1,000,000,000）沒有兩個多米諾骨牌將在 相同的位置。

內存限制：64MB

時間限制：1.00S

注：測試數據的60％的具有N≤5000

有一個強力解決方案，它解決了上述問題只有60％的投入。

看起來應該有一個次級的，甚至是線性的解決方案，使用動態編程來獲得最大輸入大小的AC。

任何提示將不勝感激。

有從作者，我也不太明白，如果它是有幫助的提示：

做一個遞歸函數f（n）的給出的移動 最低＃推翻需要頭n個多米諾骨牌。

現在你如何將f（n）與f的先前值相關？多米諾骨牌#n有兩個 的選擇：向左走（在這種情況下，它將其他多米諾骨牌倒過來），或者走 （在這種情況下，左邊的另一個多米諾骨牌將其倒過來）。嘗試從那裏工作 。

謝謝！

Answer 1

這裏是一個O(N log N)解決方案：

1. 讓我們找出如何計算什麼是下降，如果我們推i-th多米諾向左最左邊的多米諾（讓我們表示是L[i]）。想到的第一個想法是運行簡單的模擬。但那會太慢。我聲稱，當我們從左向右迭代時，我們可以維持一堆「有趣」的多米諾骨牌指數。它的僞代碼如下所示：

   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) 
   

   此代碼以線性時間運行（每一個多米諾骨牌推一次，以及彈出最多一次）。它看起來可能不是很直觀（我不會在這裏寫一個完整的形式證明，因爲它會太長），但通過手動小樣本來幫助理解爲什麼它是正確的。
   事實上，這項技術值得理解，因爲它在競爭性編程中經常使用（當某些東西從右向左移動時，我們需要找到最左邊的元素來滿足每個正確元素的一些條件，我知道這聽起來有點模糊）。

2. 我們可以用相同的方式在線性時間內計算出R[i]（如果我們將i-th多米諾骨牌推向右邊，我們可以走多遠）。

3. 現在我們知道如果我們選擇向任何方向推動任何多米諾骨牌會發生什麼。涼！

4. 讓我們使用動態規劃來計算答案。讓f(i)成爲我們需要做出的最小動作次數，這樣所有包含多達i-th的多米諾骨牌都會被擊倒，其餘的仍然未被觸動。過渡很自然：我們要麼將多米諾骨牌推向左側或向右側。在前一種情況下，我們進行轉換f(j) + 1 -> f(i)，其中L[i] - 1 <= j < i。在後一種情況下，轉換是f(i - 1) + 1 -> f(R[i])。這個解決方案是正確的，因爲它爲每個多米諾骨牌嘗試所有可能的操作。

5. 如何使這部分高效？我們需要支持兩種操作：更新點中的值並獲得範圍中的最小值。分段樹可以在O(log N)中處理它們。它給了我們一個O(N log N)解決方案。

如果此解決方案也不難，你可以先嚐試並實現一個簡單的一個：只要運行模擬計算L[i]和R[i]，然後計算定義的動態規劃陣列（無段樹）至真正理解這些問題意味着什麼（它應該得到60分）。完成之後，您可以應用堆棧和段樹優化以獲得完整的解決方案。

在案件的一些細節還不清楚，我提供正確的解決方案的實施，使你可以看看他們在那裏：

#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

你將創建一個二維陣列，其中每個小區由每個多米諾保持一對（L，R），其表示由所述特定位置

初始位置表示推壓下降骨牌（左，右）：

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

有了這個，你不想通過做一個移動來減少你的數組到< 0，0>對最小化陣列。在這種情況下移動1至R 3爲L或8至L.

對於1至R新陣列：

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

我們只1向左移動，以8至L，因此新陣列：

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

給予我們一個二維數組：

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 

因爲所有的細胞是現在< 0,0>，我們相信，人我的多米諾骨牌下降，沒有保持。

Answer 3

這個問題可以在O（N）無segtree

來解決

正如kraskevich提到的，我們需要找到從L[i] - 1到i - 1範圍內的最小值。 我們可以保留一個有趣的位置及其dp值的列表，其中位置和dp值均以升序排列。

當我們想要從範圍中查詢最小值時，我們可以輕鬆地從後面掃描列表並找到範圍內最小的有趣點。

當我們更新dp[x]後，我們將彈出列表中dp值大於dp[x]的所有點（因爲這些點不再有趣），並將(x, dp[x])添加到列表中作爲新的有趣點。

這運行在線性時間。

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]; 
}