记录编号	194315	评测结果	AAAAAAAAAA
题目名称	删数	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-10-16 14:17:45	内存使用	0.44 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#include<stack>
#define LL long long
using namespace std;
const int maxn=150;
int n,a[maxn];
LL dp[maxn][maxn];

int main(){
	freopen("remove.in","r",stdin);
	freopen("remove.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) dp[i][i]=a[i];
	for (int i=2;i<=n;++i)
	   for (int j=1;j<i;++j)
		  dp[j][i]=abs(a[i]-a[j])*(i-j+1);
	for (int len=2;len<=n;++len)
	   for (int i=1;i<=n-len+1;++i){
			int j=i+len-1;
			for (int k=i;k<j;++k)
			   dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
	   }
	printf("%lld",dp[1][n]);
	return 0;
}