用于解决这一具有挑战性的动态编程任务的指针

Question

我一直在PEG Online Judge中遇到一个问题,称为Dominos,你可以在这里找到:

http://wcipeg.com/problem/domino

简要描述:

我们给出了一个水平排列的不同高度和位置的多米诺骨牌列表.位置x的高度为h的多米诺骨牌,一旦被推向右侧,将在x + 1,x + 2,...,x + h位置向右敲击所有多米诺骨牌.相反,推向左侧的同一多米诺骨牌会将所有多米诺骨牌敲到位置x-1,x-2,...,xh向左.

推翻所有多米诺骨牌的最小推动次数是多少？

例:

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

答案是2.将多米诺骨牌推向位置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的先前值相关联？Domino #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;
}