题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6199
题意：n堆石子，Alice和Bob来做游戏，一个人选择取K堆那么另外一个人就必须取k堆或者k+1堆，两个人都想使用最优策略使得取出的石子的和的差值最大。
解法：http://blog.csdn.net/DorMOUSENone/article/details/77929439 膜大牛 用动态规划的思路来思考，每个人都想最大化自己和另外一个人的差值，其实这个题，完全可以省掉判断是谁的这一维，使得整个转移变得简单。dp[i][j]表示当前人从i开始取数取j个的最大差值。转移为：dp[i][k] = sum[i+j-1]-sum[i-1]-max(dp[i+j][j], dp[i+j][j+1])。从后往前转移，注意下标越界的问题。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20010;
//dp[i][j]表示当前这个人i从取数，取j个的最大值
//dp[i][j]=sum[i+j-1]-sum[i-1]-max(dp[i+j][j],dp[i+j][j+1])
//ans=max(dp[1][1],dp[1][2])
int a[maxn], dp[maxn][210], sum[maxn];
int main()
{
int T, n;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]), sum[i]=sum[i-1]+a[i];
int ans = -0x3f3f3f3f;
for(int i=n; i>=1; i--){
for(int j=min(200,n-i+1); j>=1; j--){
dp[i][j] = sum[i+j-1]-sum[i-1];
if(n-i-j+1>=j){
int ret = dp[i+j][j];
if(n-i-j>=j){
ret = max(ret, dp[i+j][j+1]);
}
dp[i][j] -= ret;
}
if(i==1 && j<=2) ans = max(dp[i][j], ans);
}
}
printf("%d\n", ans);
}
return 0;
}