Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「HAOI2006」数字序列 - DP

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

链接

BZOJ 1049

题解

为了方便处理边界,我们在序列最左侧添加一个 a0=mini=1n{ai} a_0 = \min\limits_{i = 1} ^ n\{ a_i \} ,最右侧添加一个 an+1=maxi=1n{ai} a_{n + 1} = \max\limits_{i = 1} ^ n\{ a_i \}

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

f(i)=maxj=0i1{f(j)+1,aiajij} f(i) = \max\limits_{j = 0} ^ {i - 1} \{ f(j) + 1, a_i - a_j \geq i - j \}

第一问答案即为 nf(n+1)+1 n - f(n + 1) + 1

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

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

cost(l,r) \mathrm{cost}(l, r) 表示l l 位置和 r r 位置不变的前提下,将 [l,r] [l, r] 一段区间修改为单调不下降序列的最小修改幅度。设 g(i) g(i) 为保证 i i 位置不变的前提下,将 [1,i] [1, i] 修改为单调不下降序列的最小修改幅度。

g(i)=minj=0i1{g(j)+cost(j,i),f(i)=f(j)+1} g(i) = \min\limits_{j = 0} ^ {i - 1} \{ g(j) + \mathrm{cost}(j, i), f(i) = f(j) + 1 \}

注意到对于方程中任意一对 (i,j) (i, j) ,不可能存在一个 k(i,j) k \in (i, j) 满足 bibkbj b_i \leq b_k \leq b_j ,即对于任意的 k(i,j) k \in (i, j) ,满足 bk>bi b_k > b_i bk<bj b_k < b_j ,即

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

枚举中间这条扫描线,维护左边若干个改变为 bj b_j ,右边若干个改变为 bi b_i 的最小代价,更新 g(i) g(i)

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

代码

#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;
}
最近的文章

「HAOI2007」覆盖问题 - 二分答案 + 枚举

用三个 L×L L \times L 的正方形覆盖一些点,使最大正方形的边长最小。

于  BZOJ, HAOI, 二分答案, 枚举 继续阅读
更早的文章

「HAOI2007」分割矩阵 - 搜索

将一个 n×m n \times m 的数字矩阵进行如下分割:将原矩阵沿某一条直线分割成两个矩阵,再将生成的两个矩阵继续如此分割(当然也可以只分割其中的一个),这样分割了 k1 k - 1 次后,原矩阵被分割成了 k k 个矩阵。(每次分割都只能沿着数字间的缝隙进行)原矩阵中每一位置上有一个分值,一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成 n n 个矩阵,并使各矩阵总分的均方差最小。请编程对给出的矩阵及 n n ,求出均方差的最小值。

于  BZOJ, DFS, DP, HAOI, 搜索 继续阅读
comments powered by Disqus