记录编号	32604	评测结果	AAAAAAAAAA
题目名称	删数	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2011-11-07 14:41:45	内存使用	0.34 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int Num[101];
long long F[101][101]; 

void init()
{
	scanf("%d\n",&N);
	for (int i=1;i<=N;i++)
		cin>>Num[i];
}

int GV(int k,int i)
{
	
	if(k==0 && i==0)
		return 0;
	
	if(k==N+1 && i==N+1)
		return 0;
	
	if(k==0)
		k++;
	if(i==N+1)
		i--;
	
	if(k==i)
		return Num[i];
	int tmp=Num[k]-Num[i];
	if(tmp<0)
		tmp=-tmp;
	return tmp*(i-k+1);
}

void dp()
{
	for (int i=1;i<=N;i++)
		F[i][0]=GV(1,i);
	
	for (int i=1;i<=N;i++)
		F[0][i]=GV(N-i+1,N);
	
	int p;
	for (int i=1;i<=N;i++)
	{
		for (int j=1;j<=N;j++)
		{
			p=i+j;
			if(p>N)
				continue;
			
			long long m=0;
			for (int k=0;k<=i;k++)
			{
				int tmp=GV(k+1,i);
				if(m<F[k][j]+ tmp )
					m=F[k][j]+ tmp;
			}
			
			F[i][j]=m;
			
			for (int k=0;k<=j;k++)
			{
				int tmp=GV(N-j+1,N-k);
				if(m<F[i][k]+tmp)
					m=F[i][k]+tmp;
			}
			
			if(m>F[i][j])
				F[i][j]=m;
		}
	}
	
	long long M=0;
	for (int i=0;i<=N;i++)
	{
		if(M<F[i][N-i])
			M=F[i][N-i];
	}
	cout<<M<<endl;
}

int main()
{
	freopen("remove.in","r",stdin);
	freopen("remove.out","w",stdout);
	init();
	
	dp();
	return 0;
}