题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1031
题目大意：两个选手，轮流可以从数组的任意一端取值， 每次可以去任意个但仅限在一端， 他们的得分分别是取得所有值的和。现在求这两个选手得分差值的最大值。
解题思路：设dp[i][j]代表从i到j这个区间中，所能够得到的最大差值，只需要枚举其中i到j之间的一个数c，作为断电，那么最大值应该为max(sum[c]-sum[i-1]-dp[c+1][j], sum[j]-sum[c-1]-cou(i, c-1))。然后在更新这一个值就行了。
代码如下：
#include <bits/stdc++.h> using namespace std;
const int N = ;
int sum[N], dp[N][N]; int cou(int i, int j)
{
if(i > j)
return ; if(dp[i][j] != INT_MAX)
return dp[i][j]; dp[i][j] = sum[j] - sum[i-];
for(int c=i; c<=j; ++ c)
{
dp[i][j] = max(dp[i][j], sum[c] - sum[i-] - cou(c+, j));
dp[i][j] = max(dp[i][j], sum[j] - sum[c-] - cou(i, c-));
} return dp[i][j];
} void solve(int cases)
{
int n;
scanf("%d", &n); for(int i=; i<=n; ++ i)
for(int j=; j<=n; ++ j)
dp[i][j] = INT_MAX; sum[] = ;
for(int i=; i<=n; ++ i)
{
scanf("%d", &sum[i]);
dp[i][i] = sum[i];
sum[i] += sum[i-];
}
printf("Case %d: %d\n", cases, cou(, n));
}
int main()
{
int t;
scanf("%d", &t);
for(int i=; i<=t; ++ i)
solve(i);
return ;
}