| 比赛 | 20110916 | 评测结果 | RRRRRRRRRR | 
    | 题目名称 | 硬币 | 最终得分 | 0 | 
    | 用户昵称 | 苏轼 | 运行时间 | 0.003 s | 
    | 代码语言 | C++ | 内存使用 | 0.30 MiB | 
    | 提交时间 | 2011-09-16 21:54:49 | 
显示代码纯文本
#include <cstdio>
using namespace std;
struct goret {
	int a, b;
};
int N, stack[2001];
goret go (int up, bool who, int last)
{
	int sum = 0;
	goret br = {0, 0};
	for (int i=0; i<last*2 && up+i<N; i++)
	{
		sum += stack[up+i];
		goret ret = go(up+i+1, !who, i+1);
		
		if (who)
		{
			ret.a += sum;
			if (ret.a > br.a)
				br = ret;
		}
		else
		{
			ret.b += sum;
			if (ret.b > br.b)
				br = ret;
		}
	}
	
	return br;
}
int main ()
{
	freopen("xonic.in", "r", stdin);
	freopen("xonic.out", "w", stdout);
	scanf("%d", &N);
	
	for (int i=0; i<N; i++)
		scanf("%d", stack+i);
	printf("%d\n", go(0, true, 1).a);
	
	return 0;
}