Poj 3134 Power Calculus（IDA*）

3134 -- Power Calculus (poj.org)

相当于是问1经过多少次能变成n，val[pos]<<(depth-now)为估计函数，如果最快都不能到n，就return false

#include<iostream>
using namespace std;
const int N=1010;
int n,pos,val[N];
bool IDAstar(int now,int depth){
    if(now>depth) return false;
    if(val[pos]<<(depth-now)<n) return false;
    if(val[pos]==n) return true;
    pos++;
    for(int i=0;i<pos;i++){
        val[pos]=val[pos-1]+val[i];
        if(IDAstar(now+1,depth)) return true;
        val[pos]=abs(val[pos-1]-val[i]);
        if(IDAstar(now+1,depth)) return true;
    }
    pos--;
    return false;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin>>n && n){
        int depth;
        for(depth=0;;depth++){
            pos=0;
            val[pos]=1;
            if(IDAstar(0,depth)) break;
        }    
        cout<<depth<<endl;
    }
    return 0;
}