银川如何做百度的网站自助建站系统代理

状态定义：

一眼区间$DP$，从左右两边删不好定义状态，不如定义$dp[i][j]$表示$[i,j]$未删的最大值，转移就很自然了

转移：

从左边删$dp[i][j]=max(dp[i][j],dp[k][j]+abs(a[i-1]-a[k])*(i-1-k+1))$

删除区间$[k,i),i-1>k$

从右边删$dp[i][j]=max(dp[i][j],dp[i][k]+abs(a[j+1]-a[k])*(k-j));$

删除区间$(j,k],k>j+1$

但是这样转移是转移不了只删一个的，特殊搞一下就好

$dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i-1])$
$dp[i][j]=max(dp[i][j],dp[i][j+1]+a[j+1])$

答案统计：

$ans=max(ans,dp[i][j]+abs(a[j]-a[i])*(j-i+1))$

答案就是$DP$数组之中，删完的最小值

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[110],dp[110][110],ans;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int l=n-1;l;l--)for(int i=1;i<=n-l+1;i++){int j=i+l-1;dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i-1]);dp[i][j]=max(dp[i][j],dp[i][j+1]+a[j+1]);for(int k=1;k<i-1;k++)dp[i][j]=max(dp[i][j],dp[k][j]+abs(a[i-1]-a[k])*(i-1-k+1));for(int k=j+2;k<=n;k++)dp[i][j]=max(dp[i][j],dp[i][k]+abs(a[j+1]-a[k])*(k-j));ans=max(ans,dp[i][j]+abs(a[j]-a[i])*(j-i+1));}printf("%d\n",ans);return 0;
}