「HAOI2006」数字序列 - DP

现在我们有一个长度为 的整数序列 。我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。

链接

BZOJ 1049

题解

为了方便处理边界,我们在序列最左侧添加一个 ,最右侧添加一个

第一问,在一个单调上升序列中,对于每一个 ,它至少要比它左边的第 个数大 ,即 。如果我们确定了一个子序列满足该条件,则只需修改剩余的数,设 表示前 个数中最长的满足该条件的序列,可以写出 DP 方程

第一问答案即为

第二问要求在第一问的前提下使修改幅度最小,即我们需要保证有一个最长的满足原单调上升条件的子序列不变。

考虑将每个数 减去 ,即令 ,显然如果 为单调不下降序列,则 为单调上升序列。问题转化为求在保证 的一个最长单调不下降子序列不变的前提下,使 单调不下降的最小修改幅度。

表示 位置和 位置不变的前提下,将 一段区间修改为单调不下降序列的最小修改幅度。设 为保证 位置不变的前提下,将 修改为单调不下降序列的最小修改幅度。

注意到对于方程中任意一对 ,不可能存在一个 满足 ,即对于任意的 ,满足 ,即

所以最优策略一定是令左边若干个改变为 ,右边若干个改变为 ,即

枚举中间这条扫描线,维护左边若干个改变为 ,右边若干个改变为 的最小代价,更新

时间复杂度(上界)为 ,但实际上远远达不到这个上界。

代码

#include <cstdio>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <algorithm>

const int MAXN = 35000;

int main() {
    int n;
    scanf("%d", &n);

    static int a[MAXN + 1];
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    static int b[MAXN + 2];
    for (int i = 1; i <= n; i++) {
        b[i] = a[i] - i;

        b[0] = std::min(b[0], b[i]);
        b[n + 1] = std::max(b[n + 1], b[i]);
    }

    static int f[MAXN + 2];
    int maxLen = 1;
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 0; j < i; j++) {
            if (b[j] <= b[i] && f[j] + 1 > f[i]) {
                f[i] = f[j] + 1;
                maxLen = std::max(maxLen, f[i]);
            }
        }
#ifdef DBG
        printf("b[%d] = %d, f[%d] = %d\n", i, b[i], i, f[i]);
#endif
    }

    printf("%d\n", n - f[n + 1] + 1);

    static int g[MAXN + 2];
    for (int i = 1; i <= n + 1; i++) {
        g[i] = INT_MAX;
        for (int j = 0; j < i; j++) {
            if (b[j] <= b[i] && f[j] + 1 == f[i]) {
                int w = 0;
                for (int k = i - 1; k > j; k--) w += abs(b[k] - b[j]);
                g[i] = std::min(g[i], g[j] + w);
                for (int k = i - 1; k > j; k--) {
                    w -= abs(b[k] - b[j]);
                    w += abs(b[k] - b[i]);
                    g[i] = std::min(g[i], g[j] + w);
                }
            }
        }
        assert(g[i] != INT_MAX);
#ifdef DBG
        printf("g[%d] = %d\n", i, g[i]);
#endif
    }

    printf("%d\n", g[n + 1]);

    return 0;
}