2017沈阳网络赛hdu6199 gems gems gems

gems gems gems

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Now there are n gems, each of which has its own value. Alice and Bob play a game with these n gems.
They place the gems in a row and decide to take turns to take gems from left to right.
Alice goes first and takes 1 or 2 gems from the left. After that, on each turn a player can take k or k+1 gems if the other player takes k gems in the previous turn. The game ends when there are no gems left or the current player can't take k or k+1 gems.
Your task is to determine the difference between the total value of gems Alice took and Bob took. Assume both players play optimally. Alice wants to maximize the difference while Bob wants to minimize it.

 

 

Input

The first line contains an integer T (1≤T≤10 ), the number of the test cases.
For each test case:
the first line contains a numbers n (1≤n≤20000 );
the second line contains n numbers: V1,V2…Vn . (−100000≤Vi≤100000 )

 

 

Output

For each test case, print a single number in a line: the difference between the total value of gems Alice took and the total value of gems Bob took.

 

 

Sample Input

1 3 1 3 2

 

 

Sample Output

4

分析：每个人取的数目和上一个人相等或多一个，第一个人想让差值最大，第二个人最小；

　　　等价于两人都想最大化自己与另一个人差值；

　　　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])；

　　　考虑后者的情况，显然是取max，即最坏情况；

　　　最后取dp[1][1]和dp[1][2]的最大值即可；

 代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <cassert>
#include <ctime>
#define rep(i,m,n) for(i=m;i<=(int)n;i++)
#define inf 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define sys system("pause")
#define ls (rt<<1)
#define rs (rt<<1|1)
#define all(x) x.begin(),x.end()
const int maxn=2e4+10;
const int N=2e5+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qmul(ll p,ll q,ll mo){ll f=0;while(q){if(q&1)f=(f+p)%mo;p=(p+p)%mo;q>>=1;}return f;}
ll qpow(ll p,ll q,ll mo){ll f=1;while(q){if(q&1)f=f*p%mo;p=p*p%mo;q>>=1;}return f;}
int n,m,k,t,a[maxn],dp[maxn][210],sum[maxn];
void upd(int &x,int y){if(x<y)x=y;}
int main(){
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        rep(i,1,n)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
        int ret=-inf;
        for(i=n;i>=1;i--)
        {
            for(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 re=dp[i+j][j];
                    if(n-i-j>=j)upd(re,dp[i+j][j+1]);
                    dp[i][j]-=re;
                }
                if(i==1&&j<=2)upd(ret,dp[i][j]);
            }
        }
        printf("%d\n",ret);
    }
    return 0;
}
/*
1
7
68 -1 25 59 -65 -46 -28
ans:112
*/