记录编号	75116	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 1996]取数游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2013-10-27 10:54:42	内存使用	0.39 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
//f[i][j]表示:在剩下[i,j]这一段之后先手的最高得分
//下一个人取:f[i+1][j]或f[i][j-1]
const int SIZEN=101;
int n;
int a[SIZEN]={0};
int f[SIZEN][SIZEN]={0};
int s[SIZEN][SIZEN]={0};
void dp(void){
	int len;
	int i,j;
	for(len=2;len<=n;len++){
		for(i=1;i<=n;i++){
			j=i+len-1;
			f[i][j]=max(s[i][j]-f[i+1][j],s[i][j]-f[i][j-1]);
		}
	}
}
void init(void){
	scanf("%d",&n);
	int i,j;
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) f[i][i]=a[i];
	for(i=1;i<=n;i++) for(j=i;j<=n;j++) s[i][j]=s[i][j-1]+a[j];
}
int main(){
	freopen("game1.in","r",stdin);
	freopen("game1.out","w",stdout);
	init();
	dp();
	printf("%d %d\n",f[1][n],s[1][n]-f[1][n]);
	return 0;
}