動態(tài)規(guī)劃法。
用dp[player][start][end]表示player在[start..end]會取得的最大值。
如果player==0，那么player有主動權(quán)，它要么選start,要么選end.顯然，它要選使得對手得分最少的那一個。
當(dāng)它選start時，對手所能到的最大值為dp[1][start+1][end]。當(dāng)它選end時，對手所選的最大值是dp[1][start][end-1].
。所以我們選dp[1][start+1][end]和dp[1][start][end-1]中小的那一個。
如果player==1，那只能被動的等0先選了。1在剩下區(qū)段中，又作為先選的角色，即player0。
當(dāng)只有一個數(shù)字的時候，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;
}