P2426 删数

有 n 个不同的正整数数 x_1,x_2,x_3...x_n 排成一排，我们可以从左边或右边去掉连续的 i (1 \leq i \leq n) 个数（只能从两边删除数），剩下 n - i 个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止

每次操作都有一个操作价值，比如现在要删除从i位置到k位置上的所有的数。操作价值为|x_i - x_k| * (k - i + 1)，如果只去掉一个数，操作价值为这个数的值问如何操作可以得到最大值，求操作的最大价值。

n \leq 100

解题思路

区间 DP,但是有两种不同的状态定义思考方式。

定义 cost_{i,j} 为删除 x_i \dots x_j 的夹指，

解法1

定义 f_{i,j} 为删除从 i 开始的 j 个数可获取的最大价值。

则初值设为最开始直接删除整段的价值，即 f_{i,j} = cost_{i,j},f_{i,1} = a_i。

由于一段数可以是删除若干段而来，我们可以枚举删除的这个分割点 k,所以有

f_{i,j} = \max(f_{i,k}+f_{i + k,j - k})

如此，我们可以直接套一个区间 DP 的模板解决即可。

时间复杂度 O(n^3)。

解法2

观察到从左右开始删数不太好直接定义状态，我们可以反面思考。

定义 f_{i,j} 为删到 x_i \dots x_j 这段数的最大价值。

由于可以从左边和右边开始删除，所以我们分两次讨论。

  1. 左边开始删除

    我们枚举一个 k, 表示删除 x_i \dots x_k 这段。则转移方程为 f_{i,j} = \max(f_{k+1,j} + cost_{i,k})

  2. 右边开始删除

    同样枚举一个 k,但 k 表示删除 x_k \dots x_j 这段。类似的，转移方程为 f_{i,j} = \max(f_{i,k-1} + cost_{k,j})

只要循环两遍即可，时间复杂度依旧是 O(n^3)

代码

解法1

for (int i = 1;i <= n;++i) {f[i][1] = a[i];}//初始化
for (int j = 2;j <= n;++j) {//枚举长度
    for (int i = 1;i <= n - j + 1;++i) {//枚举头
        f[i][j] = cost(i,i+j-1);
        for (int k = 1;k < j;++k) {
            f[i][j] = max(f[i][j],f[i][k] + f[i+k][j-k]);
        }
    }
}
int ans = 0;
for (int i = 1;i <= n;++i) ans = max(ans,f[i][n]);
printf("%d",f[1][n]);

解法2

for (int len = 2;len <= n;++len) {
    for (int i = 1;i + len - 1 <= n;++i) {
        int j = i + len - 1;
        for (int k = i;k <= j;++k) {
            f[i][j] = max(f[i][j],f[k+1][j] + cost(i,k));
        }
        for (int k = i;k <= j;++k) {
            f[i][j] = max(f[i][j],f[i][k-1] + cost(k,j));
        } 
    }
}
printf("%d",f[1][n]);