链接
https://www.luogu.org/problemnew/show/P2426
念念碎
第一次接触到区间DP（瑟瑟发抖） 所以象征性地看了一下题解 这好像是一道比较基础的区间DP吧 但是蒟蒻我还是不会啊
思路
因为是连续删除一段数字所以明显是区间DP我们不妨设f[i][j]为从i开始删除j个数字所以我们可以得到两种方案为：一起删去或者从中间某个数字分成两半分别删去于是就得到了状态转移方程：f[i][j]=max(f[i][j],f[i][k]+f[i+k][j-k])开始敲代码吧o(￣▽￣)ブ
程序实现
#include<iostream>
#include<cmath>
using namespace std;
int sum=0;
int f[501][501];
int a[501];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
f[i][1]=a[i];//从某个数字开始删掉一个的价值为本身
for(int j=2;j<=n;j++)//从删掉2个数字算起
for(int i=1;i<=n-j+1;i++)//从一开始枚举到n-j+1（因为n-j+1为最后能删掉的数字）
//例如n=7，j=2时，最多可以从6开始剪掉2个数字就是：6，7
{
f[i][j]=i*abs(a[i]-a[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]);//分成两边删掉
}
for(int i=1;i<=n;i++)
sum=max(sum,f[i][n]);//从i开始把n个数全部删掉的答案取最大
cout<<sum;
}
转载于:https://www.cnblogs.com/BrokenString/p/9279546.html
相关资源：JAVA上百实例源码以及开源项目
