记录编号	32729	评测结果	AAAAAAAAAA
题目名称	删数	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2011-11-07 21:42:06	内存使用	0.30 MiB

#include <cstdio>
using namespace std;

int f[101][101]={0};

int absint(int a)
{
	if (a<0)
		return(-a);
	else
		return(a);
}

int main(void)
{
	freopen("remove.in","r",stdin);
	freopen("remove.out","w",stdout);
	int i=0,j=0,k=0,n=0,temp=0,a[101]={0};
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (j=1;j<=n;j++)
		for (i=1;i<=n-j+1;i++)
		{
			if (a[i]+f[i+1][j-1]>a[i+j-1]+f[i][j-1])
				f[i][j]=a[i]+f[i+1][j-1];
			else
				f[i][j]=a[i+j-1]+f[i][j-1];
			for (k=i+1;k<=i+j-3;k++)
			{
				temp=f[i][k-i+1]/*+f[k+1][i+j-1-k]*/+absint(a[k+1]-a[i+j-1])*(i+j-1-k);
				if (temp>f[i][j])
					f[i][j]=temp;
				temp=absint(a[i]-a[k])*(k-i+1)+/*f[i][k-i+1]+*/f[k+1][i+j-1-k];
				if (temp>f[i][j])
					f[i][j]=temp;
			}
			temp=absint(a[i]-a[i+j-1])*j;
			if (temp>f[i][j])
				f[i][j]=temp;
		}
	printf("%d\n",f[1][n]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}