hdu6199 gems gems gems dp+博弈

/**
2017 ACM/ICPC Asia Regional Shenyang Online 解题报告
题目：hdu6199 gems gems gems
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6199
题意：Alice和Bob从左到右取数字，一开始Alice可以取1个或者2个。之后当前者可以取得数字个数为k或者k+1个。
k为上一个人选的数字个数。如果当前者选不到k个或者k+1个，那么游戏结束。
两个人都用最科学的方法取数字。问Alice的total value - Bob的total value最大。
思路：dp+博弈 由于k*(k+1)<=2e4；所以k不超过200；
定义dp[i][k]表示从i开始取数字，可以取k个或者k+1个可以获得的最大差值。

dp[i][k] = max(sum[i+k-1]-dp[i+k][k],sum[i+k]-dp[i+k+1][k+1])-sum[i-1];

当前自己选的数的和-下一个人可以获得的最大差值=自己可以获得的最大差值。

比赛的时候搞错了题意。。。
时限1000ms
dfs做法超时。
改为递推200多ms。
*/
#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x,y,sizeof x)
const int maxn  = 2e4+10;
const int inf = 0x3f3f3f3f;
int n;
int v[maxn], dp[maxn][202];
int sum[maxn];
/*
int dfs(int i,int k)
{
    if(i+k-1>n) return 0;
    if(i+k-1==n) return sum[n]-sum[i-1];
    if(vis[i][k]) return dp[i][k];
    vis[i][k] = true;
    int &res = dp[i][k];
    res = max(sum[i+k-1]-sum[i-1]-dfs(i+k,k),sum[i+k]-sum[i-1]-dfs(i+k+1,k+1));
    return res;
}*/
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d",&v[i]);
        for(int i = 1; i <= n; i++) sum[i] = sum[i-1]+v[i];
        ms(dp,0);
        for(int i = n; i >= 1; i--){
            for(int k = 200; k >= 1; k--){
                if(i+k-1>n) continue;
                if(i+k-1==n) dp[i][k] = sum[n]-sum[i-1];///选k个。
                else{
                    dp[i][k] = max(sum[i+k-1]-dp[i+k][k],sum[i+k]-dp[i+k+1][k+1])-sum[i-1];
                }
            }
        }
        printf("%d
",dp[1][1]);
    }
    return 0;
}

/*
10
3
1 3 2
2
1 -1
3
1 1 1
4
2 2 3 3
2
1 2
*/