记录编号	41956	评测结果	AAAAAAAAAA
题目名称	硬币	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.223 s
提交时间	2012-09-06 21:02:48	内存使用	18.42 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int s[2001];
int f[2001][2001];
int a[2001];
int i,j,k,n,m;
int max(int a,int b){
	if (a>b) return a;else return b;
}
int main()
{
	freopen("xoinc.in","r",stdin);
	freopen("xoinc.out","w",stdout);
	scanf("%d",&n);
	for (i=n;i>=1;i--){
		scanf("%d",&a[i]);
	}
	s[0]=0;
	for (i=1;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]=max(f[i][j],f[i][j-1]);
			if (i-2*j>=0){
				f[i][j]=max(s[i]-f[i-(2*j)][2*j],f[i][j]);
			}
			if (i-2*j+1>=0){
				f[i][j]=max(f[i][j],s[i]-f[i-(2*j-1)][2*j-1]);
			}
		}
	printf("%d",f[n][1]);
	return 0;
}