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()); } }