题解 P2426 【删数】
sukimo
2020-04-07 20:20:18
一道比较基础的dp，不过其思想还是十分的经典。如果是新手，那么建议把此题深入体会。
首先设计状态：$dp[i]$表示前i个数进行删除的最大值。由于这题是可以从两端删，所以看成区间
dp，开一个二维数组的做法也是可行的。不过一维做法明显更加精简。
那么我们接下来关注状态转移方程，这是dp的重中之重。(先抛出来看看)：
$dp[i]=max\{val(1,i),dp[j]+val(j+1,i)\}(1\le j\le i-1)$
其中，$val$是一个估价函数(默认左端点小于等于右端点)，它代表删除一个区间的价值。首先，前$i$个数可以一次删完，也可以分多次删。如果一次删，那么直接就是$val(1,i)$。如果要多次删，我们就要找到对于第$i$个数，它和哪些数一起删除是最优的。这时枚举$j$，用来找第$i$个数和哪些数一起删除。$dp[j]$代表和$i$无关的部分删除最大价值(这里体现了dp的转移性)，而$val(j+1,i)$则是和$i$一起删除的价值。
最终结果：$dp[n]$
上代码：
```
#include<bits/stdc++.h>
using namespace std;
int array[105],dp[105];
int val(int x,int y){return x==y?array[x]:abs(array[y]-array[x])*(y-x+1);}
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&array[i]);dp[i]=val(1,i);
for(int j=1;j<=i-1;j++)dp[i]=max(dp[i],dp[j]+val(j+1,i));
}
printf("%d",dp[n]);
return 0;
}
```
谢谢观赏！！