想到快速幂 但是这题用不上
用迭代加深搜索
注意启发函数为 当前最大数<<(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>=;i--)
{
a[d+]=a[d]+a[i];
if(dfs(d+,maxx))return true; a[d+]=a[d]-a[i];
if(a[d+]>)
if(dfs(d+,maxx))return true;
}
return false;//一定要加
}
int solve(void)
{
a[]=;
for(int maxx=;;maxx++)
if(dfs(,maxx))return maxx ;
} int main()
{
while(scanf("%d",&n),n)
{
printf("%d\n",solve());
}
}