记录编号	27368	评测结果	AATTTTTTTT
题目名称	硬币	最终得分	20
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	8.024 s
提交时间	2011-09-19 19:04:07	内存使用	0.27 MiB

#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("xoinc.in", "r", stdin);
	freopen("xoinc.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;
}