学步园

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. 

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].

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.

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

-3
0
1

POJ Monthly--2004.06.27 srbga@POJ

/*
 * Author:  ******
 * Created Time:  2013/10/7 12:44:23
 * File Name: A.cpp
 * solve: A.cpp
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<iostream>
#include<vector>
#include<queue>
//ios_base::sync_with_stdio(false);
//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(x) memset(x,0,sizeof(x))
#define clrs( x , y ) memset(x,y,sizeof(x))
#define out(x) printf(#x" %d\n", x)
#define sqr(x) ((x) * (x))
typedef long long LL;

const int INF = 1000000000;
const double eps = 1e-8;
const int maxn = 20000;

int sgn(const double &x) {  return (x > eps) - (x < -eps); }
int n,a,b;
int num[maxn];
int dp[maxn];//dp[i]代表先手取第i个数时的最优解
int dfs(int cur)
{
    if(dp[cur] != -1)
        return dp[cur];
    
    int ans = -INF;
    repf(i,cur+1,n)
    {
        if(num[i] - num[cur] >= a && num[i] - num[cur] <= b)
        {
            int  temp = dfs(i);//后手一定取最优解
            if(temp > ans)
                ans = temp;
        }
    }
    
    if(ans == -INF)
        ans = 0;
    
    dp[cur] = num[cur] - ans;
    return dp[cur];
}
int main() 
{
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        clrs(dp,-1);
        scanf("%d%d%d",&n,&a,&b);
        repf(i,1,n)
            scanf("%d",&num[i]);
        
        sort(num+1,num+1+n);
        
        int ans = -INF;
        repf(i,1,n)
        {
            if(num[i] >= a && num[i] <= b)
            {
                ans = max(ans,dfs(i));
            }
        }
        
        if(ans == -INF)
            cout<<"0"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}