|
I Love this Game!
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 |
题意：有N个数，有一个区间[A,B],第一个人先取一个数x（A<=x<=B），后一次取必须
比第一个数大，而且差值在区间内。问最后两个人取的数的和的差值最大为多少。
思路：dp[i]表示如果先手取了第i个数，可以达到的最大分差。那么最后一次取的分差就
是本身。dp[ i ] = a[ i ] - max(dp[ j ]) ( i < j ) , 其意义为第一个人取第 i 个后，然后就相当
第二个人现在变成了先手，即他要保证最大分差。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int inf=1<<30;
const int maxn=10010;
int dp[maxn],a[maxn],n,l,r;
void input()
{
scanf("%d %d %d",&n,&l,&r);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
}
void initial()
{
for(int i=0;i<n;i++) dp[i]=-inf;
}
int DP(int x)
{
if(dp[x]!=-inf) return dp[x];
int ans=-inf;
for(int i=x+1;i<n;i++)
if(a[i]-a[x]>=l && a[i]-a[x]<=r)
ans=max(ans,DP(i));
if(ans==-inf) dp[x]=a[x];
else dp[x]=a[x]-ans;
return dp[x];
}
void solve()
{
int Max=-inf;
for(int i=0;i<n;i++)
if(a[i]>=l && a[i]<=r)
Max=max(Max,DP(i));
if(Max==-inf) printf("0\n");
else printf("%d\n",Max);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
input();
initial();
solve();
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
poj 1678 I Love this Game!（博弈dp）
原文：http://blog.csdn.net/u012596172/article/details/46722651