UVa 1374 快速幂计算（dfs+IDA*）

题意：给出n，计算最少需要几次能让x成为x^n（x和已经生成的数相乘或相除）。

思路：IDA*算法。

如果当前数组中最大的数乘以1<<（maxd-d）<n（即一直让最大的数相乘都无法到达n次方），此时可以剪枝。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 1005;
 7 
 8 
 9 int n;
10 int ans[maxn];
11 int maxd;
12 
13 bool dfs(int d, int cur)  //深度、当前新增数
14 {
15 
16     if ((cur == n && d == maxd) || cur << (maxd - d) == n)  return true;  //得到目标状态
17                                                                          //如果当前新增数乘以1<<(maxd-d)等于n，就可以成功
18     //int r = 0;
19     //for (int i = 0; i <= d; i++)  r = max(ans[i], r);
20     //r = max(cur, r);
21     //if (d > maxd || r << (maxd - d) < n)  return false;  //剪枝
22     if (d > maxd || cur << (maxd - d) < n)  return false;  //剪枝
23     ans[d] = cur;
24     for (int i = 0; i <= d; i++)
25     {
26         if (dfs(d + 1, cur + ans[i]))       return true;
27         if (dfs(d + 1, abs(cur - ans[i])))  return true;
28     }
29     return false;
30 }
31 
32 void solve()
33 {
34     for (maxd = 0;; maxd++)
35     {
36         ans[0] = 1;
37         if (dfs(0, 1))
38         {
39             cout << maxd << endl;
40             return;
41         }
42     }
43 }
44 
45 int main()
46 {
47     //freopen("D:\txt.txt", "r", stdin);
48     while (cin >> n && n)
49     {
50         solve();
51     }
52     return 0;
53 }