题目大意:
用最小的步数算出 x^n
思路:
直接枚举有限步数可以出现的所有情况。
然后加一个A* 就是如果这个数一直平方 所需要的步骤数都不能达到最优 就剪掉
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std; int n;
int save[1005]={1};
int h(int val)
{
if(val==0)return 0x3f3f3f3f; int cnt=0;
while(val<n)
{
val*=2;
cnt++;
}
return cnt;
}
bool dfs(int dep,int lit,int top)
{
if(dep>lit)return false; for(int i=0;i<top;i++)
{
save[top]=save[top-1]+save[i]; if(save[top]==n)return true;
if(dep+h(save[top])>lit)continue;
if(dfs(dep+1,lit,top+1))return true; save[top]=abs(save[top-1]-save[i]);
if(save[top]==n)return true;
if(dep+h(save[top])>lit)continue;
if(dfs(dep+1,lit,top+1))return true;
}
return false;
}
int main()
{
while(scanf("%d",&n)!=EOF && n)
{
save[0]=1;
if(n==1)printf("0\n");
else
for(int lit=1;;lit++)
{
if(dfs(1,lit,1))
{
printf("%d\n",lit);
break;
}
}
}
return 0;
}