在此游戏中任意时刻的状态都是原始序列的一段子序列故：
定义d(i, j) : 表示原来序列的第i ~ j个元素组成的子序列，在双方都采取最优策略的情况下，先手得分的最大值、
状态转移时，需要枚举从左边或者从右边取多少个。因此
d(i, j) = sum[i, j] - min{d(i+1, j), d(i + 2, j).....d(j, j) , d(i, j-1), d(i, j-2),, ... , d(i, i), 0}
其中sum[i, j] 是元素i 到j 的和。这里的0是取完所有的数， 有了它方程就不需要显式的边界条件了。
答案是 d(1, n) - (sum[1, n] - d(1, n)) = 2*d(1, n) - sum[1, n]
先手 后手
记忆话一下就可以了
#include<stdio.h>
#include<string.h>
#include<algorithm> using namespace std;
#define MAXN 110
#define inf 100000000 int dp[MAXN][MAXN];
int z[MAXN];
int sum[MAXN];
bool vis[MAXN][MAXN]; int d(int a,int b)
{
if(vis[a][b])
return dp[a][b];
vis[a][b]=;
int m=;
int i;
for(i=a+;i<=b;i++)m=min(m,d(i,b));
for(i=a;i<=b;i++)m=min(m,d(a,i));
dp[a][b]=sum[b]-sum[a-]-m;
return dp[a][b];
}
int main()
{
int t,ca;
scanf("%d",&t);
ca=; while(t--)
{
int n,i;
scanf("%d",&n);
memset(vis,,sizeof(vis));
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
scanf("%d",&z[i]);
sum[i]=sum[i-]+z[i];
} printf("Case %d: %d\n",ca++,*d(,n)-sum[n]);
}
return ;
}