Luogu P2426 删数 解题报告

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]);