题意：输入正整数n(1<=n<=1000)，问最少需要几次乘除法可以从x得到x的n次方，计算过程中x的指数要求是正的。
题解：这道题，他的结果是由1经过n次加减得到的，所以最先想到的就是暴力回溯，其中的剪枝函数，首先不能得到重复的数，其次深度有上限，上限是n-1,还有，如果当前序列的最大数乘以2的(dep-cnt)(dep与cnt分别表示深度上限和当前深度)次方小于n，则剪枝。但是这样的时间复杂度还是特别高，所以又想到了另外的方法，就是先列出深度，然后找在这个深度里是否存在一个方法得到n
代码：
1 #include<math.h> 2 #include<vector> 3 #include<string.h> 4 #include<stdio.h> 5 #include<iostream> 6 using namespace std; 7 const int maxn=1010; 8 int n,minn,dep; 9 int ans[maxn]; 10 11 bool dfs(int num,int cnt){ 12 if(cnt==dep){ 13 if(num==n) 14 return 1; 15 return 0; 16 } 17 if(num*(1<<(dep-cnt))<n) return 0; 18 for(int i=cnt;i>=0;i--){ 19 ans[cnt+1]=ans[i]+num; 20 if(dfs(ans[i]+num,cnt+1)){ 21 return 1; 22 } 23 if(ans[i]<num){ 24 ans[cnt+1]=num-ans[i]; 25 if(dfs(num-ans[i],cnt+1)){ 26 return 1; 27 } 28 } 29 else if(ans[i]<num){ 30 ans[cnt+1]=ans[i]-num; 31 if(dfs((ans[i])-num,cnt+1)) 32 return 1; 33 } 34 } 35 return 0; 36 } 37 38 //bool dfs(int num,int cnt){ 39 // if(num==n){ 40 // return 1; 41 // } 42 // if(cnt==dep){ 43 // return 0; 44 // } 45 // if(num*(1<<dep-cnt)<n) return 0; 46 // for(int i=0;i<=cnt;i++){ 47 // for(int j=1;j<=2;j++){ 48 // if(j==1){ 49 // ans[cnt+1]=num+ans[i]; 50 // if(dfs(num+ans[i],cnt+1)){return 1;} 51 // } 52 // else{ 53 // ans[cnt+1]=num-ans[i]; 54 // if(num-ans[i]<0) continue; 55 // if(dfs(num-ans[i],cnt+1)) return 1; 56 // } 57 // } 58 // } 59 // return 0; 60 //} 61 62 int main(){ 63 //freopen("in.txt","r",stdin); 64 while(scanf("%d",&n)&&n){ 65 minn=1024; 66 memset(ans,0,sizeof(ans)); 67 ans[0]=1; 68 for(dep=0;dep<=13;dep++){ 69 if(dfs(1,0)) 70 break; 71 } 72 printf("%d ",dep); 73 } 74 }