解题思路：
这是一道以快速幂计算为原理的题，实际上也属于求最短路径的题目类型。那么我们可以以当前求出的幂的集合为状态，采用IDA＊方法即可求解。问题的关键在于如何剪枝效率更高。笔者采用的剪枝方法是：
1）如果当前状态幂集合中的最大元素max满足 max＊2^（maxd－cur_d）<n，则剪枝。原因是：在每一次状态转移后，max最多增大一倍。（maxd－cur_d）次转移之后，max最多变成原来的2^（maxd－cur_d）倍，然而如果当前状态的极限情况下仍有max<n，则当前状态结点一定无法出解。
2）解的幂集合中最多只有一个元素比目标n大。
采用反证法，证明如下：
假设解的幂集合中存在m2>m1>n ，那么必然存在从m2到达m1的路径p1，和从m1到达n的路径p2（否则与假设矛盾）。
设路径p1花费步数s1，路径p2花费步数s2，那么从m2到达n的步数为s3=s2＋s1>s2。
然而由于我们采用IDA＊算法，由于s2<s3，路径p2会先被找到，当前状态不会出现，产生矛盾，得证。
有了以上优化思路，代码效率将会极大提高。
代码如下：
1 #include <iostream> 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <ctime> 6 #include <set> 7 #include <algorithm> 8 9 using namespace std; 10 #define time__ printf("time : %f ",double(clock())/CLOCKS_PER_SEC) 11 12 int tar_n; 13 int power[3000+5]; 14 vector<int> S; 15 int maxd; 16 int S_upper_n(){ 17 int cnt=0; 18 for(int i=0;i<S.size();i++) 19 if(S[i]>tar_n) cnt++; 20 return cnt; 21 } 22 bool dfs(int d){ 23 if(d==maxd){ 24 if(power[tar_n]) return true; 25 else return false; 26 } 27 int S_max=0; 28 for(int i=0;i<S.size();i++) 29 S_max=max(S_max,S[i]); 30 if(((S_max)<<(maxd-d))<tar_n||S_upper_n()>1) 31 return false; 32 for(int i=S.size()-1;i>=0;i--){ 33 int t; 34 t=S[S.size()-1]+S[i]; 35 if(power[t]==0){ 36 S.push_back(t); 37 power[t]=1; 38 if(dfs(d+1)) return true; 39 S.pop_back(); 40 power[t]=0; 41 } 42 t=S[S.size()-1]-S[i]; 43 if(t>0&&power[t]==0){ 44 S.push_back(t); 45 power[t]=1; 46 if(dfs(d+1)) return true; 47 S.pop_back(); 48 power[t]=0; 49 } 50 } 51 return false; 52 } 53 bool solve(){ 54 memset(power, 0, sizeof power); 55 S.clear(); 56 S.push_back(1); 57 power[1]=1; 58 if(dfs(0)) 59 return true; 60 return false; 61 } 62 int main() { 63 while(scanf("%d",&tar_n)&&tar_n){ 64 maxd=0; 65 int temp=1; 66 while(temp<tar_n){ 67 maxd++; 68 temp+=temp; 69 } 70 for(;;maxd++) 71 if(solve()){ 72 printf("%d ",maxd); 73 //time__; 74 break; 75 } 76 } 77 //time__; 78 return 0; 79 }