记录编号	27379	评测结果	AAAAAAAAAA
题目名称	硬币	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	C++	运行时间	0.239 s
提交时间	2011-09-19 20:53:25	内存使用	34.62 MiB

#include <iostream>
#include <fstream>

using namespace std;

int n,i,j,k,l;
int a[3000],s[3000],f[3000][3000];

int max(int x,int z)
{
	if (x<z)
		x=z;
	return x;
}

int main()
{
	ifstream fin("xoinc.in");
	ofstream fout("xoinc.out");
	
	fin>>n;
	for (i=n;i>=1;i--)
		fin>>a[i];
	s[1]=a[1];
	for (i=2;i<=n;i++)
		s[i]=s[i-1]+a[i];
	
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			f[i][j]=f[i][j-1];
			if ((i-(2*j-1))>=0)
				f[i][j]=max(f[i][j],s[i]-f[i-(2*j-1)][2*j-1]);
			if ((i-2*j)>=0)
				f[i][j]=max(f[i][j],s[i]-f[i-2*j][2*j]);
		}
	
	fout<<f[n][1];
	
	fin.close();
	fout.close();
	
	return 0;
}