hdu 6199 gems gems gems（DP）

gems gems gems

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1518    Accepted Submission(s): 349

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
  
  

解：俩个人轮流取数，一个想使差值变大 一个人想使差值变小 （这里difference是差值的意思） 那么本质就是两个人都想尽可能多的取到大的数字

就算每次取数的数量都加一 最多也只能取200个状态 所以用二维数组表示 第一维&255 状态压缩 降低内存使用 这里用倒序取数来表示每个人每次的最优取数策略

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 20000+1105;
typedef long long LL;
const int mod = 255;
typedef long long LL;
int a[N], dp[300][225], sum[N];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d", &a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        if(n==1)
        {
            printf("%d\n",a[1]);
            continue;
        }
        memset(dp,0,sizeof(dp));
        for(int i=n;i>=1;i--)
        {
            for(int j=205;j>=1;j--)
            {
                if(i+j-1==n) dp[i&mod][j]=sum[n]-sum[i-1];
                else if(i+j-1<=n)
                {
                    int x=0;
                    if(i+j+j-1<=n) x=dp[(i+j)&mod][j];
                    if(i+j+j<=n) x=max(x,dp[(i+j)&mod][j+1]);
                    dp[i&mod][j]=sum[i+j-1]-sum[i-1]-x;
                }
            }
        }
        printf("%d\n",max(dp[1&mod][1],dp[1&mod][2]));
    }
    return 0;
}