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 ;
}
05-11 18:09
查看更多