记录编号	27370	评测结果	AAAAAAAAAA
题目名称	硬币	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.202 s
提交时间	2011-09-19 19:37:04	内存使用	15.55 MiB

#include <cstdio>
const int MAXN = 2002;
int n, f[MAXN][MAXN], s[MAXN+1], ans;
inline int max(int a, int b) {
	return a>b ? a : b;
}
inline int max(int a, int b, int c) {
	return max(a, max(b, c));
}
int main() {
	freopen("xoinc.in", "r", stdin);
	freopen("xoinc.out", "w", stdout);
	scanf("%d", &n);
	for(int i=n; i>0; i--)
		scanf("%d", s+i);
	for(int i=1; i<=n; i++)
		s[i] += s[i-1];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			f[i][j] = max(f[i][j-1],
				(i-j*2+1)>=0 ? s[i] - f[i-j*2+1][j*2-1] : 0,
				(i-j*2)>=0 ? s[i] - f[i-j*2][j*2] : 0);
	ans = f[n][1];
	printf("%d\n", ans);
	return 0;
}