题目地址：http://vjudge.net/problem/UVA-10891
题目是博弈，双方都是采用最优的解法，所以要枚举所有可能的取法
状态：d[i][j]代表i~j，先手得分的最大数值（A，B都会成为先手）
状态转移：（枚举所有取法）A取i~k ,i<=k<j 或者k~j，j>=k>i 复杂度为O(n) ，选择A分数高的作为决策
比如A若取i~k， 那么还剩下k+1~j 那么状态转移到d(k+1,j) （其代表B为先手，取得的最大值）,A要大代表B要小，即在所有d中取最小的（B越小，A才大，A+B为定值）
所以d[i][j]=score(i,j)-d[k+1,j] ，也就是i~j的总分- B在此[k+1,j]区间的最小值，就是A在i~j的最大值
状态有O(n*n) 转移有O(n) 所以复杂度为O(n*n*n)
记忆化递归法：
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=100+3;
int S[maxn],d[maxn][maxn];
bool vis[maxn][maxn];
int DP(int i,int j){if(vis[i][j]) return d[i][j];vis[i][j]=true;int m=0;REP(k,i+1,j) m=min(m,DP(k,j));REPD(k,j-1,i) m=min(m,DP(i,k));return d[i][j]=S[j]-S[i-1]-m;
}
int main(int argc, char const *argv[])
{int n,x; while(scanf("%d",&n)==1&&n){REP(i,1,n) {scanf("%d",&x);S[i]=S[i-1]+x;}memset(vis,false,sizeof(vis));printf("%d\n", 2*DP(1,n)-S[n]);}return 0;
}
就是用一个数组f[][]保存 REP(k,i+1,j) m=min(m,DP(k,j)); 这一步的答案，f[][]也可以通过递推求得，f[i][j]=min(d[i][j],f[i+1][j]
同理 g[i][j] 优化 REPD(k,j-1,i) m=min(m,DP(i,k)); g[i][j]=min(d[i][j],g[i][j+1]
状态转移为O(1)
所以复杂度为O(n*n)
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=100+3;
int S[maxn],d[maxn][maxn],f[maxn][maxn],g[maxn][maxn];
int main(int argc, char const *argv[])
{int n,x; while(scanf("%d",&n)==1&&n){REP(i,1,n) scanf("%d",&x),S[i]=S[i-1]+x,f[i][i]=g[i][i]=d[i][i]=x; //只剩一个,先手只能拿这个REP(L,1,n-1) REP(i,1,n-L) {int j=i+L;int m=0;m=min(m,f[i+1][j]);m=min(m,g[i][j-1]);d[i][j]=S[j]-S[i-1]-m;f[i][j]=min(d[i][j],f[i+1][j]);g[i][j]=min(d[i][j],g[i][j-1]);}printf("%d\n", 2*d[1][n]-S[n]);}return 0;
}