解决这一具有挑战性的动态规划任务的指针

Question

我在PEG在线法官中遇到了一个名为Dominos的问题，您可以在这里找到：

http://wcipeg.com/problem/domino

摘要描述：

我们得到了一张不同高度和位置的多米诺骨牌的列表，这些多米诺骨牌是水平排列的。高度为h的x位置的多米诺骨牌一旦向右推，就会在x+1，x+2，.，x+h右击所有的多米诺骨牌。相反，向左推的同一张多米诺骨牌会在x-1，x-2，.，x-h左边击倒所有多米诺骨牌。

我们可以做的最小推动次数是多少来推翻所有骨牌？

示例：

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

答案是2__。向右推多米诺骨牌，向左推多米诺骨牌。

Constraints:

输入以单个整数N≤100,000开始，多米诺骨牌数，后面是N对整数。每一对整数表示多米诺骨牌的位置和高度。(1≤height≤1,000,000,000，1≤≤1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 内存限制:64 Memory 时限:1.00秒 注: 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=i=0 .N-1虽然我们可以通过将i推到左边的s.top()多米诺，但s.top()是我们不能打的最右边的多米诺骨牌(如果s是空的，我们可以击打所有的多米诺骨牌)s.push(第一个多米诺) 此代码以线性时间运行(每个多米诺骨牌精确推送一次，最多弹出一次)。这似乎不是很直观(我不会在这里写一个完整的正式证明，因为它太长了)，但是手动处理小示例可以帮助理解为什么它是正确的。 实际上，这种技术是值得理解的，因为它通常用于竞争性编程(当某些东西从右向左移动时，我们需要找到满足每个右元素的某些条件的最左边元素。我知道这听起来有点模糊)。
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

这个问题可以在没有分段树的O(N)中得到解决。

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

Answer 3

您将创建一个2D数组，其中每个单元格都有一对(L，R)，表示特定位置下的多米诺骨牌。

初始位置由每个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>

这样，就不会通过将数组减少到<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>，我们确信所有的多米诺骨牌都倒下了，没有一个能坚持住。