algorithm - 解决这一具有挑战性的动态规划任务的建议

Question

我一直被 PEG Online Judge 中的一个问题困住了，这个问题叫做 Dominos，你可以在这里找到它:

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

答案是2。将位置 1 的多米诺骨牌向右推，位置 8 的多米诺骨牌向左推。

约束:

The input starts with a single integer N ≤ 100,000, the number of dominoes, followed by N pairs of integers. Each pair of integers represents the location and height of a domino. (1 ≤ location ≤ 1,000,000,000, 1 ≤ height ≤ 1,000,000,000) No two dominoes will be in the same location.

Memory Limit: 64mb

Time Limit: 1.00s

NOTE: 60% of test data has N ≤ 5000.

有一种蛮力解决方案，只能解决 60% 的输入问题。

看起来应该有使用动态规划的次二次甚至线性解决方案，以便获得最大输入大小的 AC。

如有任何提示，我们将不胜感激。

作者有一个提示，我不太明白，以防有帮助:

Make a recursive function f(n) that gives the minimum # of moves required to topple the first n dominoes.

Now how do you relate f(n) to previous values of f? Domino #n has two choices: go left (in which case it topples other dominoes over) or go right (in which case another domino to its left topples it over). Try working from there.

谢谢!

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