poj 3134 Power Calculus(IDA*)

题目大意：

用最小的步数算出 x^n

思路：

直接枚举有限步数可以出现的所有情况。

然后加一个A* 就是如果这个数一直平方 所需要的步骤数都不能达到最优 就剪掉

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; int n; int save[1005]={1}; int h(int val) { if(val==0)return 0x3f3f3f3f; int cnt=0; while(val
        
         lit)return false; for(int i=0;i
         
          lit)continue; if(dfs(dep+1,lit,top+1))return true; save[top]=abs(save[top-1]-save[i]); if(save[top]==n)return true; if(dep+h(save[top])>lit)continue; if(dfs(dep+1,lit,top+1))return true; } return false; } int main() { while(scanf("%d",&n)!=EOF && n) { save[0]=1; if(n==1)printf("0\n"); else for(int lit=1;;lit++) { if(dfs(1,lit,1)) { printf("%d\n",lit); break; } } } return 0; }