正題

鏈接 需要紀中OJ賬號
有n個數，可以選擇刪除一段區間，價值為|xi – xk|*(k-i+1)。求刪完所有數的最大價值

---

輸入輸出（需要自取）

Input 　　
輸入文件的第一行為一個正整數N，第二行有N個用空格隔開的N個不同的正整數。
Output
輸出文件包含一個正整數，為操作的最大值
Sample Input
6 54 29 196 21 133 118
Sample Output
768

---

解題思路

刪除一個區間，就很快想到這就是區間dp，然后就使用了曾經石子合并問題的做法。

---

代碼

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,a[101],f[101][101]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);for (int i=1;i<=n;i++)for (int j=i;j<=n;j++){if (i==j) f[i][j]=a[i];else f[i][j]=abs(a[i]-a[j])*(j-i+1);//初始化為所有區間直接刪}for (int k=2;k<=n;k++)//多個多個合并{for (int i=1;i<=n;i++){int j=i+k;if (j<=n)for (int d=i;d<j;d++)f[i][j]=max(f[i][j],f[i][d]+f[d+1][j]);//看看分開刪還是一起刪價值更大}}printf("%d",f[1][n]);//刪除1到N的數 } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【2018.3.17】模拟赛之二-ssl1862jzoj1366 删数【区间dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。