记录编号	28707	评测结果	AAAAAAAAAA
题目名称	硬币	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.213 s
提交时间	2011-10-17 09:59:26	内存使用	15.55 MiB

#include<iostream>
#include<fstream>
#include<cmath>

using namespace std;

int c[2002],f[2001][2001],n;

void work()
{
	int i,j;
	for(i=1;i<=n;i++)
		f[0][i]=0;
	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],c[i]-f[i-2*j+1][2*j-1]);
			if(i-2*j>=0)
				f[i][j]=max(f[i][j],c[i]-f[i-2*j][2*j]);
		}
}

int main()
{
	int i;
	ifstream fin("xoinc.in");
	ofstream fout("xoinc.out");
	fin>>n;
	for(i=n;i>0;i--)
		fin>>c[i];
	for(i=1;i<=n;i++)
		c[i]+=c[i-1];
	work();
	fout<<f[n][1]<<endl;
	fin.close();
	fout.close();
	return 0;
}