动态规划法。
用dp[player][start][end]表示player在[start..end]会取得的最大值。
如果player==0，那么player有主动权，它要么选start,要么选end.显然，它要选使得对手得分最少的那一个。
当它选start时，对手所能到的最大值为dp[1][start+1][end]。当它选end时，对手所选的最大值是dp[1][start][end-1].
。所以我们选dp[1][start+1][end]和dp[1][start][end-1]中小的那一个。
如果player==1，那只能被动的等0先选了。1在剩下区段中，又作为先选的角色，即player0。
当只有一个数字的时候，player0就只有选这个，player1就没得选，返回0.
代码如下：
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("game1.in");
ofstream fout("game1.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
int dp[2][100][100];
int sequence[100];
int score(int player,int start,int end)
{
if(dp[player][start][end]!=-1)
return dp[player][start][end];
if(start==end){
if(player==0)
dp[player][start][end] = sequence[start];
else
dp[player][start][end] = 0;
}else{
int t1 = score(0,start+1,end);
int t2 = score(0,start,end-1);
if(player==0){
if(t1>t2){
dp[player][start][end] = sequence[end]+score(1,start,end-1);
}else{
dp[player][start][end] = sequence[start]+score(1,start+1,end);
}
}else{
if(t1>t2){
dp[player][start][end] = score(0,start,end-1);
}else{
dp[player][start][end] = score(0,start+1,end);
}
}
}
return dp[player][start][end];
}
void solve()
{
memset(dp,-1,sizeof(dp));
int size;
in>>size;
for(int i=0;i<size;++i)
in>>sequence[i];
out<<score(0,0,size-1)<<" "<<score(1,0,size-1)<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}