POJ 1678

博弈题，使用DP来完成。开始时，我以为可以用极大极小加剪枝可以过，但，TLE。。。

看过一些题解，没看懂，但也由此有了启发：

我们只记录差（初始为0），那为1选的数即为在原差值上加上该数，2选即是减去该数。那么，可以有以下的式子来表达这一过程

ANS=A-B+C-D+E-F；

神奇的事情来了，将式子转换一下ANS=A-（B-（C-（D-（E-F））））；把TMP=（B-（C-（D-（E-F））））；

很明显，我们得到了一个递归的式子。怎么理解呢？这样想，1选了A之后，即到B选。那么，2肯定希望选择后的TMP（也表示一个差值）最大，使得总的差值最小。那么2选后，1却希望总的差值最大，那么，它也只需使得它选之后的C-（D-（E-F）最大（慢慢分析，你会发现是对的）。这里，很显然有一个无后效性。于是，可以采用记忆化搜索来完成。

妙。。。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int inf=(<<);

 int num[],dp[];

 int n,A,B;

 int work(int m){

     if(dp[m]!=-inf)

     return dp[m];

     int ans=-inf;

     for(int i=m+;i<n;i++){

         int tmp=num[i]-num[m];

         if(tmp>B) break;

         if(tmp>=A&&tmp<=B){

             ans=max(ans,work(i));

         }

     }

     if(ans==-inf){

         dp[m]=num[m];

     }

     else {

         dp[m]=num[m]-ans;

     }

     return dp[m];

 }

 void slove(){

     int ans=-inf;

     for(int i=;i<n;i++){

         if(num[i]>=A&&num[i]<=B){

             ans=max(ans,work(i));

         }

     }

     if(ans==-inf)

     printf("0\n");

     else printf("%d\n",ans);

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         scanf("%d%d%d",&n,&A,&B);

         for(int i=;i<n;i++){

             dp[i]=-inf;

             scanf("%d",&num[i]);

         }

         sort(num,num+n);

         slove();

     }

     return ;

 }

巴特西

POJ 1678

最新文章

热门文章