题意：

输入n，问最少需要几次乘除法可以从x得到x^n

 

每次从当前状态集和找两个数相加减

只需要用刚搜出的数 与之前的数即可

 

#include
     
      using namespace std;int n,maxd;int ans[1001]={
   1};bool dfs(int d){    int pre=ans[d-1];    if(d==maxd+1) return pre==n;    if((pre<
      
       
        =0;i--)    {        ans[d]=pre+ans[i];        if(ans[d]==n || dfs(d+1)) return true;        ans[d]=pre-ans[i];        if(ans[d]>0 && (ans[d]==n || dfs(d+1))) return true;    }    return false;} int main(){    while(scanf("%d",&n)!=EOF)    {         if(!n) return 0;         if(n==1)  { printf("0\n"); continue; }         for(maxd=1;;maxd++)          {             if(dfs(1)) break;         }         printf("%d\n",maxd);        // for(int i=0;i<=maxd;i++) printf("%d ",ans[i]);    }}