POJ1678[I Love this Game!]

博弈动归，方程f[i]=pool[i]-max{f[next[i]]}，从后往前推，next[i]表示可能为i的后继的值。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-6-18

DESCRIPTION:

http://acm.pku.edu.cn/JudgeOnline/problem?id=1678

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <vector>

using std::vector;

#include <algorithm>

using std::sort;

 

class Application

{

      int t,n,a,b;

      vector<int> pool;

      int get()

      {

          const int oo=~(1<<31);

          sort(pool.begin(),pool.end());

          //f[i]=pool[i]-max{f[next[i]]}

          vector<int> f(n,-oo);

          int answer=-oo;

          bool have_first=false;

          for (int i=n-1;i>=0;i–)

          {

              bool have_next=false;

              for (int j=i+1;j<n;j++)

                  if (a<=pool[j]-pool[i]

                      &&pool[j]-pool[i]<=b

                      &&f[i]<f[j])

                     f[i]=f[j],

                     have_next=true;

              if (have_next) f[i]=pool[i]-f[i];

              else f[i]=pool[i];          

              if (a<=pool[i]

                  &&pool[i]<=b

                  &&answer<f[i])

                 answer=f[i],

                 have_first=true;

          }

          if (!have_first) answer=0;

          return answer;

      }

      public:

      Application()

      {

                   std::ios::sync_with_stdio(false);

      }

      int run()

      {

          cin>>t;

          for (int i=0;i<t;i++)

          {

              cin>>n>>a>>b;

              pool.resize(n);

              for (int j=0;j<n;j++)

                  cin>>pool[j];

              cout<<get()<<endl;

              pool.clear();

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}