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

#include<fstream>
using namespace std;
ifstream fin("remove.in");
ofstream fout("remove.out");
long long n,Xi[103],f[103][103],g[103][103],Max;
void init()
{
int i;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>Xi[i];
}

int abs(int Obj)
{
	if(Obj<0)
		return 0-Obj;
	else
		return Obj;
}

void dp()
{
int i,j,k;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
		{
			Max=0;
			for(k=1;k<i;k++)
				if(Max<f[k][i-1])
					Max=f[k][i-1];
			if(i==j)
				f[i][j]=Max+Xi[i];
			else
				f[i][j]=Max+abs(Xi[j]-Xi[i])*(j-i+1);
		}
}

int main()
{
int i;
	init();
	
	dp();	
	for(i=1;i<=n;i++)
	{
		if(f[i][n]>Max)
			Max=f[i][n];
	}
		fout<<Max<<endl;
	fin.close();
	fout.close();
	return 0;
}