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+;

const int inf = 0x3f3f3f3f;

int n;

int v[maxn], dp[maxn][];

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 = ; i <= n; i++) scanf("%d",&v[i]);

        for(int i = ; i <= n; i++) sum[i] = sum[i-]+v[i];

        ms(dp,);

        for(int i = n; i >= ; i--){

            for(int k = ; k >= ; k--){

                if(i+k->n) continue;

                if(i+k-==n) dp[i][k] = sum[n]-sum[i-];///选k个。

                else{

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

                }

            }

        }

        printf("%d\n",dp[][]);

    }

    return ;

}

/*

10

3

1 3 2

2

1 -1

3

1 1 1

4

2 2 3 3

2

1 2

*/