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

https://vjudge.net/problem/UVA-1374

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

思路：IDA*算法。

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

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 int n;

 int ans[maxn];

 int maxd;

 bool dfs(int d, int cur)  //深度、当前新增数

 {

     if ((cur == n && d == maxd) || cur << (maxd - d) == n)  return true;  //得到目标状态

                                                                          //如果当前新增数乘以1<<(maxd-d)等于n，就可以成功

     //int r = 0;

     //for (int i = 0; i <= d; i++)  r = max(ans[i], r);

     //r = max(cur, r);

     //if (d > maxd || r << (maxd - d) < n)  return false;  //剪枝

     if (d > maxd || cur << (maxd - d) < n)  return false;  //剪枝

     ans[d] = cur;

     for (int i = ; i <= d; i++)

     {

         if (dfs(d + , cur + ans[i]))       return true;

         if (dfs(d + , abs(cur - ans[i])))  return true;

     }

     return false;

 }

 void solve()

 {

     for (maxd = ;; maxd++)

     {

         ans[] = ;

         if (dfs(, ))

         {

             cout << maxd << endl;

             return;

         }

     }

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     while (cin >> n && n)

     {

         solve();

     }

     return ;

 }