POJ 3134 Power Calculus (迭代剪枝搜索)

题目大意：略

题目里所有的运算都是幂运算，所以转化成指数的加减

由于搜索层数不会超过$2*log$层，所以用一个栈存储哪些数已经被组合出来了，不必暴力枚举哪些数已经被搜出来了

然后跑$iddfs$就行了

可以加一个剪枝，设你选择的最大迭代深度为K，现在如果当前组合出的数$x$，满足$x*2^{K-dep}<n$，说明$n$一定无法被$x$组合出来(即自己不断加自己)，$x$对于答案是一定无意义的，就跳出

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define NN 2010

 #define ll long long

 #define uint unsigned int

 #define ull unsigned long long

 #define inf 0x3f3f3f3f

 #define idx(X,Y) ((X)*5+(Y))

 using namespace std;

 const int maxn=;

 int vis[NN],use[NN],bin[],a[NN];

 int n;

 int stk[NN],num;

 int dfs(int dep,int s,int ma)

 {

     if(s==n) return ;

     if(dep>=ma) return ;

     int ans;

     if(s*(<<ma-dep)<n) return ;

     for(int i=;i<=num;i++)

     {

         int x=stk[i];

         if(use[s+x]) continue;

         use[s+x]=,stk[++num]=s+x;

         ans=dfs(dep+,s+x,ma);

         use[s+x]=,stk[num--]=;

         if(ans) return ;

         if(s-x<||use[s-x]) continue;

         use[s-x]=,stk[++num]=s-x;

         ans=dfs(dep+,s-x,ma);

         use[s-x]=,stk[num--]=;

         if(ans) return ;

     }

     return ;

 }

 int main()

 {

     //freopen("t2.in","r",stdin);

     bin[]=;

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

         bin[i]=bin[i-]<<;

     for(int s=;s<=maxn;s++)

         a[s]=s;

     while(scanf("%d",&n)&&n!=)

     {

         if(n==) {printf("0\n");continue;}

         memset(use,,sizeof(use));

         int ans;use[]=;

         num=,stk[++num]=;

         for(int k=;k<=;k++){

             ans=dfs(,,k);

             if(ans){ans=k;break;}

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

     }

     return ;

 }

巴特西

POJ 3134 Power Calculus (迭代剪枝搜索)

最新文章

热门文章