记录编号	32645	评测结果	AAAAAAAAAA
题目名称	删数	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2011-11-07 15:54:22	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define max(a,b) ((a)>=(b)?(a):(b))
using namespace std;
int n,a[110],q[110][110],w[110][110];
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]);
		w[i][i]=a[i];
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			w[i][j]=abs((double)(a[j]-a[i]))*(j-i+1);
		}
	}
	for (int i=1;i<=n;i++)
		q[i][0]=w[1][i];
	for (int i=1;i<=n;i++)
        q[0][i]=w[n-i+1][n];
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (i+j>n)
			{
				continue;
			}
			int temp1=0;
			for (int k=0;k<=i;k++)
			{
				if (q[k][j]+w[k+1][i]>temp1)
				{
					temp1=q[k][j]+w[k+1][i];
				}
			}
			int temp2=0;
			for (int k=0;k<=j;k++)
			{
				temp2=max(temp2,q[i][k]+w[n-j+1][n-k]);
			}
			q[i][j]=max(temp1,temp2);
		}
	}
	int answer=0;
	for (int i=1;i<=n;i++)
	{
		if (q[i][n-i]>answer)
		{
			answer=q[i][n-i];
		}
	}
	cout<<answer;
	return 0;
}