POJ_1678

    如果我们把差在[a,b]的范围内的两个数之间连一条边的话，就会发现实际上取数的过程就是在有向无环图上行走的过程，对于一个点来讲，如果选择了它，并把选择它的人看作先手的话，那么之后的选择形成的先手与后手的分差唯一的，于是我们就可以把选择每个节点看作一个状态并进行记忆化搜索。

    于是可以用f[i]表示如果当前选第i个数，并把选择这个数的人看作先手，从这个选择开始后续形成的分差的最大值。同时，在dp的过程中我们要认为后手选择的是最优的情况，所以有f[i]=a[i]-max{f[j]}，其中a[i]表示第i个数的值，j为i的后继。

#include
     
       #include
      
        #include
       
         #define INF 0x3f3f3f3f #define MAXD 10010 int N, A, B, a[MAXD], f[MAXD]; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p, *q = (int *)_q; return *p - *q; } void init() {
   int i, j, k;     scanf("%d%d%d", &N, &A, &B); for(i = 0; i < N; i ++)         scanf("%d", &a[i]);     qsort(a, N, sizeof(a[0]), cmp); } int dfs(int cur) {
   if(f[cur] != -1) return f[cur]; int i, j, k, ans = -INF; for(i = cur + 1; i < N && a[i] - a[cur] <= B; i ++) if(a[i] - a[cur] >= A && (k = dfs(i)) > ans)             ans = k; if(ans == -INF)         ans = 0; return f[cur] = a[cur] - ans; } void solve() {
   int i, j, k, ans = -INF;     memset(f, -1, sizeof(f[0]) * N); for(i = 0; i < N; i ++) if(a[i] >= A && a[i] <= B && (k = dfs(i)) > ans)             ans = k;     printf("%d\n", ans == -INF ? 0 : ans); } int main() {
   int t;     scanf("%d", &t); while(t --)     {
           init();         solve();     } return 0; }