7-13 Power Calculus 快速幂计算 uva1374

想到快速幂  但是这题用不上 

用迭代加深搜索

注意启发函数为  当前最大数<<(maxx-d)  如果大于n则剪枝  

注意跳出语句的两种写法   一种170ms  一种390ms ！！！

dfs最后的false一定要加   

#include<bits/stdc++.h>
using namespace std;
#define N 1000
int n;
int a[N];

bool dfs(int d,int maxx)
{   
    
    if(a[d]==n)return true;
    if(d==maxx)return false;
     
   // if(d>maxx)return false;
   //  if(a[d]==n)return true;上面两条语句用下面这两条代替整整慢了一倍时间

    if( (a[d]<<(maxx-d))<n )return false;

    for(int i=d;i>=0;i--)
    {
        a[d+1]=a[d]+a[i];
        if(dfs(d+1,maxx))return true;
        
        a[d+1]=a[d]-a[i];
       if(a[d+1]>0)
            if(dfs(d+1,maxx))return true;
    }
   return false;//一定要加
}
int solve(void)
{
    a[0]=1;
    for(int maxx=0;;maxx++)
      if(dfs(0,maxx))return maxx ;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        printf("%d
",solve());
    }
}