题目链接:
https://vjudge.net/problem/UVA-1374
题意:
给定一个数n,让你求从1至少要做多少次乘除才可以从 x 得到 xn。
题解:
首先这个是幂级的,次数不会很多,所以可以考虑IDA*算法,这个算法并不难,难在找乐观函数h(x),
这个题乐观函数可以是当前最大数*2^(maxd - d) 小于n,回溯。很好理解,最大的数再一直乘2都达不到,最终肯定达不到。
其实是关于指数的操作,即从1到m最少的步数。我们可以先确定最少步数m,然后进行迭代,迭代的过程也就是判断通过相加减所得到的数可以在m次操作中等于n,如果符合,m即为最小步数,如果不符合,m++,进行下一次迭代。迭代过程中要注意剪枝,即剩余的次数如果每次都是取最大值相加还是比n小的话,就直接跳出。
再就是应该先试乘再试除,还有不要出现负整数
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int n,maxd,A[maxn]; 19 20 bool dfs(int cur,int now){ 21 if(now<<(maxd-cur)<n || cur>maxd || now<0) 22 return false; 23 if(now==n || now<<(maxd-cur)==n) //估值函数 24 return true; 25 26 A[cur] = now; 27 for(int i=0; i<=cur; i++){ 28 if(dfs(cur+1,now+A[i])) return true; 29 if(dfs(cur+1,now-A[i])) return true; 30 } 31 return false; 32 } 33 34 int main(){ 35 while(cin>>n && n){ 36 for(maxd=0; ; maxd++) 37 if(dfs(0,1)) break; 38 cout << maxd << endl; 39 } 40 41 return 0; 42 }