【极大化剪枝】Power Hungry Cows-C++【没有用A*！】【超级简单！】

Description
小KITTY想要快速计算整数P的幂 (1 <= P <=10,000),它们需要你的帮助。因为计算极大数的幂，所以它们同一时间仅能使用2个存储器，每个存储器可记录某个结果值。第一件工作是初始化存储器内的值一个为底数x，另一个为1。小KITTY可以相乘或相除2个存储器中的值，并把结果存在其中某个存储器内，但所有存储的结果必须是整数。
例如, 如果他们想计算x^31, 一种计算方法是:
WV1 WV2
开始: x 1
存储器1和存储器1相乘，结果存于存储器2: x x^2
存储器2和存储器2相乘，结果存于存储器2: x x^4
存储器2和存储器2相乘，结果存于存储器2: x x^8
存储器2和存储器2相乘，结果存于存储器2: x x^16
存储器2和存储器2相乘，结果存于存储器2: x x^32
存储器2和存储器1相除，结果存于存储器2: x x^31
因此, x^31可以通过6次计算得出。给出要计算的幂次，要求求出最少需要几次计算。
Input
仅一个整数: P
Output
仅一个整数：最少计算次数。
Sample Input
31
Sample Output
6

提醒一下：爆搜样例都过不了是真的会爆
这篇博客主要是讲不用A*怎么优化代码不TLE的。
这道题目网上有很多做法，但是正解都统一到了一个知识点：

A*启发型搜索
这个东西很麻烦，会引申到知识点：

哈希表
估价函数
以及很多…
完全不是搜索初学者能够完成的一道题目！！！！

但是！
这道题目真的有这么麻烦吗？
这里需要普及一种算法：

极大化剪枝
这是个好东西！就是这个算法让我能够不碰A*就能写出代码。
什么是极大化剪枝呢？
每个有效状态都使得它之后的所有状态极大化，如果这样都无法得到最终的答案，那么这个状态是一个无解的状态，可以剪枝。
这个极大化剪枝对程序时间的控制有多大的作用呢？
这么说吧：

当我的代码没有A*，没有极大化剪枝的时候，p=500我需要6000ms,但是加了极大化剪枝，p=500只需要0ms就可以跑出来。
怎么实现呢？其实很简单，这道题目的极大化剪枝的难点就在于怎么模拟每个状态之后所有状态极大化所得到的值呢？

这道题目还用到了分支限界
因为这不是重点，所以简单说一下：
分支限界，每次都规定搜索的深度，如果深度到达了规定的限度，不管是否达到目标状态，都要退出搜索。
分支限界的好处在于可以减少DFS的搜索量，能够快速的计算输出最优解的步数（或者是其他）
通常定义一个全局变量（lim）,然后在主函数里面写：

 for(lim=;;lim++)

     dfs...

相应的，DFS里的返回条件，变成了：

 if(深度超限)

 {

     if(达到目标状态)

     {

         进行操作

     }

     return;

 }

这样就达到了分支限界的效果了.
极大化剪枝怎么实现呢？
在什么情况下，就算在极限状态下也无法让a或b大于等于p？
只有当a,b中较大的在极限次数范围内不停自加，最终结果还是＜p的时候，当前状态是无解的。
那么我们就可以开一个数组，下标为i的存储2的i次方（预处理数组），然后拿a,b较大数乘剩下的操作次数（lim-dep+1）为下标的预处理数组，如果结果还小于p，那么就剪枝.。
然后加上网上搜集整理的剪枝：（为了方便处理，a一定是大于等于b的）

 if(a==b)return;

 if(a>p&&b==)return;

 if(p%__gcd(a,b)!=)return;

 if(a>*p)return;

不要问为什么我也不会证
另外就是拓展问题。
看到有些大佬是拓展了12种方案的，但是做减法的四种可以优化一下，只弄2种：

dfs(abs(a-b),b,s+);

dfs(a,abs(a-b),s+);

然后自除太弱鸡我直接删了
就只剩下8种拓展方案：

 dfs(a+b,b,s+);

 dfs(a,a+b,s+);

 dfs(abs(a-b),b,s+);

 dfs(a,abs(a-b),s+);

 dfs(a*,b,s+);

 dfs(a,a*,s+);

 dfs(a,b*,s+);

 dfs(b*,b,s+);

完整代码也很简单，至少比什么A*简单多了

 #include<bits/stdc++.h>

 using namespace std;

 int p,cnt,lim,st,ed,cut[]={};

 void dfs(int a,int b,int s)

 {

     if(a<=b)swap(a,b);

     if(s>lim)

     {

         if(a==p||b==p)

         {

             cout<<s<<endl;

             exit();

         }

         return;

     }

     if(a*cut[lim-s+]<=p)return;

     if(a==b)return;

     if(a>p&&b==)return;

     if(p%__gcd(a,b)!=)return;

     if(a>*p)return;

     if(a<&&b<)return;

     dfs(a+b,b,s+);

     dfs(a,a+b,s+);

     dfs(abs(a-b),b,s+);

     dfs(a,abs(a-b),s+);

     dfs(a*,b,s+);

     dfs(a,a*,s+);

     dfs(a,b*,s+);

     dfs(b*,b,s+);

 }

 int main()

 {

     cin>>p;

     if(p==||p==)

     {

         cout<<<<endl;

         return ;

     }

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

     {

         cut[i]=cut[i-]*;

     }

     for(lim=;;lim++)

         dfs(,,);

     return ;

 }

经过这番优化，10个点总用时只有惊人的16ms

ov.

巴特西

【极大化剪枝】Power Hungry Cows-C++【没有用A*！】【超级简单！】

最新文章

热门文章