紫书搜索 例题7-13 UVA - 1374 Power Calculus迭代深搜+剪枝 IDA*

题目链接:

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小的话，就直接跳出。

再就是应该先试乘再试除，还有不要出现负整数

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; int n,maxd,A[maxn]; bool dfs(int cur,int now){ if(now<<(maxd-cur)<n || cur>maxd || now<0) return false; if(now==n || now<<(maxd-cur)==n) //估值函数 return true; A[cur] = now; for(int i=0; i<=cur; i++){ if(dfs(cur+1,now+A[i])) return true; if(dfs(cur+1,now-A[i])) return true; } return false; } int main(){ while(cin>>n && n){ for(maxd=0; ; maxd++) if(dfs(0,1)) break; cout << maxd << endl; } return 0; }