链接

https://www.luogu.org/problemnew/show/P2426

---

念念碎

第一次接触到区间DP（瑟瑟发抖）

所以象征性地看了一下题解

这好像是一道比较基础的区间DP吧

但是蒟蒻我还是不会啊

---

思路

1. 因为是连续删除一段数字所以明显是区间DP
2. 我们不妨设f[i][j]为从i开始删除j个数字
3. 所以我们可以得到两种方案为：一起删去或者从中间某个数字分成两半分别删去
4. 于是就得到了状态转移方程：f[i][j]=max(f[i][j],f[i][k]+f[i+k][j-k])
5. 开始敲代码吧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;

}