UVA 10891 - Game of Sum DP

有一个长度为n的整数序列，A和B轮流取数，A先取，每次可以从左端或者右端取一个或多个数，所有数都被取完时游戏结束，然后统计每个人取走的所有数字之和作为得分，两人的策略都是使自己的得分尽可能高，并且都足够聪明，求A的得分减去B的得分的结果。

思路：

跟着作者做的~这题是题很好的dp

设dp[i][j]为第i~j先手取得的最大值。

那么dp(i,j)=sum(i,j)-min{ dp(i+1,j),dp(i+2,j).....dp(j,j), dp(i,j-1),dp(i,-2j)....dp(i,i) ,0} 0表示全部取完。

以为答案为A-B的得分，所以ans=dp[1][n]-(sum[1][n]-dp[1][n])=2*dp[1][n]-sum[1][n]；

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=110; int a[MAXN],sum[MAXN],dp[MAXN][MAXN],vis[MAXN][MAXN]; int dfs(int i,int j) { if(vis[i][j]) return dp[i][j]; vis[i][j]=1; int m=0; for(int k=i+1;k<=j;k++) m=min(m,dfs(k,j) ); for(int k=i;k