记录编号	32769	评测结果	AAAAAAAAAA
题目名称	删数	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2011-11-08 12:35:38	内存使用	0.26 MiB

#include <fstream>

#define I_F "remove.in"
#define O_F "remove.out"

const short MAXn=100;

int s[MAXn];
short n;
long ans;

void Input();
inline long Max(const long, const long);
inline long Abs(const long);
void Dynap();
void Output();

int main()
{
	Input();
	Dynap();
	Output();
	return 0;
}

void Input()
{
	std::ifstream fin(I_F);
	fin>>n;
	for (short i=0; i<n; i++)
		fin>>s[i];
	fin.close();
}

inline long Max(const long a, const long b)
{
	return (a>b)?a:b;
}

inline long Abs(const long x)
{
	return (x<0)?-x:x;
}

void Dynap()
{
	long f[MAXn+1][MAXn+1]={{0}};
	for (short i=0; i<=n; i++)
		for (short j=0; j<=n-i; j++)
		{
			for (short k=0; k<j; k++)
				f[i][j]=Max(f[i][j],f[i][k]+((j-k>1)?((j-k)*Abs(s[n-k-1]-s[n-j])):s[n-j]));
			for (short k=0; k<i; k++)
				f[i][j]=Max(f[i][j],f[k][j]+((i-k>1)?((i-k)*Abs(s[i-1]-s[k])):s[i-1]));
		}
		
	ans=0;
	for (short i=0; i<=n; i++)
		ans=Max(ans,f[i][n-i]);
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<ans<<std::endl;
	fout.close();
}