现在的位置: 首页 > 综合 > 正文

poj 1678 I Love this Game!(博弈dp)

2014年09月29日 ⁄ 综合 ⁄ 共 2060字 ⁄ 字号 评论关闭
I Love this Game!
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 1707   Accepted: 657

Description

A traditional game is played between two players on a pool of n numbers (not necessarily distinguishing ones). 

The first player will choose from the pool a number x1 lying in [a, b] (0 < a < b), which means a <= x1 <= b. Next the second player should choose a number y1 such that y1 - x1 lies in [a, b] (Attention! This implies y1 > x1 since a > 0). Then the first player
should choose a number x2 such that x2 - y1 lies in [a, b]... The game ends when one of them cannot make a choice. Note that a player MUST NOT skip his turn. 

A player's score is determined by the numbers he has chose, by the way: 

player1score = x1 + x2 + ... 
player2score = y1 + y2 + ... 

If you are player1, what is the maximum score difference (player1score - player2score) you can get? It is assumed that player2 plays perfectly. 

Input

The first line contains a single integer t (1 <= t <= 20) indicating the number of test cases. Then follow the t cases. Each case contains exactly two lines. The first line contains three integers, n, a, b (2 <= n <= 10000, 0 < a < b <= 100); the second line
contains n integers, the numbers in the pool, any of which lies in [-9999, 9999].

Output

For each case, print the maximum score difference player1 can get. Note that it can be a negative, which means player1 cannot win if player2 plays perfectly.

Sample Input

3
6 1 2
1 3 -2 5 -3 6
2 1 2
-2 -1
2 1 2
1 0

Sample Output

-3
0
1

Source

题意:2个人轮流拿数组里面的一个数,且要比另外一个人上一次拿的数大【a,b】,第一次拿要拿【a,b】范围的数

题解:听说这是一道博弈dp什么,由于第一次听,就拿了这题理解了一下,我的理解如下

           对于每一个人其实的状态都是要取自己的值减去别人的值尽量大,那么设dp【i】为本轮取了i后获得的最大值

          由于下一轮是要使他的值最大,就是会使本轮的值最小,那么一定会选一个可以调转的使对方值最小的状态,所以

          dp【i】=min(dp【i】,c【j】-dp【j】),其中a《=c【j】-c【i】《=b,并且j是别人挑选的,所以会使本轮的dp值最小

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 100000008
using namespace std;
int c[10008],dp[10008];
int main()
{
    int t,n,a,b,i,j;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&a,&b);
        for(i=0;i<n;i++)
        {
            scanf("%d",c+i);
            dp[i]=inf;
        }
        sort(c,c+n);
        dp[n-1]=c[n-1];
        for(i=n-2;i>=0&&c[i]>=a;i--)
        {
            for(j=i+1;j<n&&c[j]-c[i]<=b;j++)
            {
                if(c[j]-c[i]>=a)
                    dp[i]=min(dp[i],c[i]-dp[j]);
            }
            if(dp[i]==inf) dp[i]=c[i];
        }
        int res=-inf;
        for(i=0;i<n&&c[i]<=b;i++)
        {
            if(c[i]<a) continue;
            if(dp[i]>res) res=dp[i];
        }
        if(res==-inf) printf("0\n");
        else printf("%d\n",res);
    }

    return 0;
}

抱歉!评论已关闭.