题意：
给n个数，A,B两人轮流取，每次可从左右其中一边取1或多个数，两个人都尽量使自己取的数总和最大，问最终sumA-sumB最大为多少。
由于两个人取的数总和是一定的，所以只要求出先取的那个最多有多少就行了。
用dp[i][j]表示a[i..j]这一段数中先取的人能取到的最大和。（这里的先取意思是表示这在一段先取，不是A的意思）
先取的人可能取左边任意一段a[i..i],a[i..i+1],a[i...i+2]....a[i,j]或右边任意一段a[j...j],a[j-1...j],a[j-2..j]....a[i,j]
那么另一个人就有可能从a[i+1...j]、a[i+2....j],a[j..j],0,a[i..i],a[i...i+1],a[i..i+2]...a[i...j-1]中取。0表示已经被取完，也就是边界。
要让dp[i][j]最大，最要让另一个人从剩下的数中能取到的最大值最小
dp[i][j]=sum[i][j]-min{ dp[i+1][j] , dp[i+2][j] , ... dp[j][j] , 0 , dp[i][i+1] , dp[i][i+2] , dp[i][j-1] };
状态数是n^2,每个状态的转移有2n个，所以总复杂度为O(n^3)对于这题的n<=100的数据量已经足够
最终的结果就是dp[1][n]-(sum[1][n]-dp[1][n])=2*dp[1][n]-sum[1][n];
int da[110]; int sum[110]; int dp[110][110]; int vis[110][110]; int f(int l,int r) { if(vis[l][r])return dp[l][r]; vis[l][r]=1; int m=0; for(int i=l;i<r;i++) { m=min(m,f(l,i)); } for(int i=r;i>l;i--) { m=min(m,f(i,r)); } return dp[l][r]=sum[r]-sum[l-1]-m; } int main() { int n; while(scanf("%d",&n)!=EOF&&n) { sum[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&da[i]); sum[i]=sum[i-1]+da[i]; } memset(vis,0,sizeof(vis)); printf("%d ",2*f(1,n)-sum[n]); } return 0; }
但是还能把状态的转移优化
设f[i][j]=min{ f[i][k] | i<=k<=j }; g[i][j] = min{ g[k][j] | i<=k<=j };
那么dp[i][j] = sum[i][j] - min{ f[i][j-1] , g[i+1][j] , 0}
f[i][j]和g[i][j]也可以同样递推得到
复杂度便降到O(n^2)
int da[110]; int sum[110]; int dp[110][110]; int g[110][110]; int f[110][110]; int main() { int n; while(scanf("%d",&n)!=EOF&&n) { sum[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&da[i]); sum[i]=sum[i-1]+da[i]; } for(int len=0;len<n;len++) { for(int i=1;i+len<=n;i++) { if(len>0) { int m; int j=i+len; m=min(f[i][j-1],g[i+1][j]); m=min(m,0); dp[i][j]=sum[j]-sum[i-1]-m; f[i][j]=min(f[i][j-1],dp[i][j]); g[i][j]=min(g[i+1][j],dp[i][j]); } else { dp[i][i]=da[i]; f[i][i]=da[i]; g[i][i]=da[i]; } } } printf("%d ",2*dp[1][n]-sum[n]); } return 0; }