优化：将一个数组分成长度不大于k的连续子序列，使得每个子序列中最大值的和最小。

Question

优化：将一个数组分成长度不大于k的连续子序列，使得每个子序列中最大值的和最小。

11

将 O(n^2) 算法优化到 O(n log n)。

问题描述

给定由 n 个正整数组成的数组 A。将该数组划分为长度不超过 k 的连续子序列，使得每个子序列中的最大值之和最小。以下是一个例子。

如果 n = 8，k = 5，数组元素为 1 4 1 3 4 7 2 2，最优解是 1 | 4 1 3 4 7 | 2 2。总和为 max{1} + max{4, 1, 3, 4, 7} + max{2, 2} = 1 + 7 + 2 = 10。

O(n^2) 解法

设 dp[i] 为问题描述中子问题数组 A[0] ... A[i] 的最小和。当 i=0 时，有 dp[0]=A[0]；对于 0<i<n（其中 dp[-1]=0），有：

dp[i] = min(0, i-k+1 <= j <= i)(dp[j - 1] + max{A[j], ..., A[i]})

// A, n, k, - defined
// dp - all initialized to INF
dp[0] = A[0];
for (auto i = 1; i < n; i++) {
    auto max = -INF;
    for (auto j = i; j >= 0 && j >= i-k+1; j--) {
        if (A[j] > max)
            max = A[j];
        auto sum = max + (j > 0 ? dp[j-1] : 0);
        if (sum < dp[i])
            dp[i] = sum;
    }
}
// answer: dp[n-1]

O(n log n)？

问题的作者声称可以在 O(n log n) 时间内解决，有些人能够通过测试案例。如何进行优化？

- aquablitz11

4

您当前的算法时间复杂度为O(n*k)，因为第二个循环不能回顾超过"k"步以前的数据。 - Sergey Kalinichenko

在找到最小化dp [i]的j之后，如果发现这个j导致最终段具有严格少于k个元素，则此j也将为dp [i + 1]提供有效解决方案。让m成为dp [i]的最佳解决方案中最终段中的最大元素。 A [i + 1]可以是> m或<= m; 考虑是否可以在每种情况下消除一些测试。 - j_random_hacker

想知道这个问题在现实世界中的一个示例应用，有什么想法吗？ - Eric

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- md5 · Accepted Answer

注意：我将稍微更改您的动态规划关系，以便在j = 0时没有特殊情况。现在dp[j]是前j个项A [0]，...，A [j-1]的答案，并且：

dp[i] = min(dp[j] + max(A[j], ..., A[i-1]), i-k <= j < i)

问题的答案现在是dp[n]。

请注意，如果j < i且dp[j] >= dp[i]，则您将不需要在以下转换中使用dp[j]，因为max(A[j],...,A[l])>=max(A[i],...,A[l])（因此在 j 而不是j处剪切始终更好）。

此外，让C[j] = max(A[j + 1], ..., A[l])（其中l是动态编程步骤中的当前索引，即您的C ++程序中的i）。

然后，您可以在内存中保留一些索引集合x1 < ... < xm（用于动态规划关系的转换的“有趣”索引），使得：dp[x1] < ... < dp[xm]（1）。然后自动C [x1] >= ... >= C [xm]（2）。

要存储{x1，...，xm}，我们需要一些支持以下操作的数据结构：

弹出后面（当我们从i移动到i + 1时，我们必须说i-k现在是不可达的）或前面（参见插入）。
推前x（当我们计算dp[i]时，通过删除相应元素来保留（1）插入它）。
计算min(dp [xj] + C [xj]，1 <= j <= m)。

因此，一些队列用于存储x1，...，xk以及一个set用于存储所有dp [xi] + C [xi]将足够。

当我们插入元素 i 时，我们如何同时保留（1）并更新C？

在计算dp[i]之前，我们使用A[i-1]更新C。为此，我们查找集合x中最小的元素xj，使得C[xj] <= A[i-1]。然后(1)和(2)意味着对于所有j' >= j，都有dp[j'] + C[j'] >= dp[j] + C[j]，因此我们将C[xj]更新为A[i-1]，并从集合中删除x(j+1), ..., xm。
插入dp[i]时，我们只需通过弹出头部来删除所有满足dp[j] >= dp[i]的元素。
当我们删除i-k时，可能会发生一些元素在(*)中被破坏，现在正在成为最佳的情况。因此，如果必要，我们将更新C并插入最后一个元素。

复杂度：O(n log n)（集合中最多可能有2n个插入操作）。

以下代码概括了主要思路：

template<class T> void relaxmax(T& r, T v) { r = max(r, v); }

vector<int> dp(n + 1);
vector<int> C(n + 1, -INF);
vector<int> q(n + 1);
vector<int> ne(n + 1, -INF);
int qback = 0, qfront = 0;
auto cmp = [&](const int& x, const int& y) {
    int vx = dp[x] + C[x], vy = dp[y] + C[y];
    return vx != vy ? vx < vy : x < y;
};
set<int, decltype(cmp)> s(cmp);

dp[0] = 0;
s.insert(0);
q[qfront++] = 0;

for (int i = 1; i <= n; ++i) {
    C[i] = A[i - 1];
    auto it_last = lower_bound(q.begin() + qback, q.begin() + qfront, i, [=](const int& x, const int& y) {
        return C[x] > C[y];
    });

    for (auto it = it_last; it != q.begin() + qfront; ++it) {
        s.erase(*it);
        C[*it] = A[i - 1];
        ne[*it] = i;
        if (it == it_last) s.insert(*it);
    }

    dp[i] = dp[*s.begin()] + C[*s.begin()];

    while (qback < qfront && dp[q[qfront]] >= dp[i]) {
        s.erase(q[qfront]);
        qfront--;
    }

    q[qfront++] = i;
    C[i] = -INF;
    s.insert(i);

    if (q[qback] == i - k) {
        s.erase(i - k);

        if (qback + 1 != qfront && ne[q[qback]] > q[qback + 1]) {
            s.erase(q[qback + 1]);
            relaxmax(C[q[qback + 1]], C[i - k]);
            s.insert(q[qback + 1]);
        }

        qback++;
    }
}

// answer: dp[n]

这次我针对你的算法进行了压力测试：点击这里查看。如有不清楚的地方，请告知。