题解 SP7579 【YOKOF - Power Calculus】

会打沙包的猫 · 2019-07-25 17:40:25 · 题解

迭代加深搜索的关键就是枚举边界， 虽然可能造成重复， 但实际上寻找最优解的时候， 可以规避一些很深的支路，来优化dfs的效率 .一句话总结：获得了bfs特性的dfs

下面直接贴代码（注释）

#pragma GCC optimize(2)
//手动开氧气，是我最后的倔强
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int stt[100],floor;
//stt是存步骤，floor存限制步数
int n;
int dfs(int step,int now)
{
    if(step>floor)return false;
    //关键语句
    if(!(now>0))return false;
    //可行性剪枝
    if((now<<(floor-step))<n)return false;
    //可行性剪枝
    if((now<<(floor-step))==n)return true;
    //估计答案
    if(now==n)return true;
    //找到答案
    stt[step]=now;
    //存储路径
    for(int i=0;i<=step;i++)
    {
        if(dfs(step+1,now+stt[i]))
          return true;
          //深搜的下一步是乘法
        if(dfs(step+1,now-stt[i]))
          return true;
          //深搜的下一步是除法
    }
    return 0;
}
int main()
{
    while(1)
    {
        floor=0;
        scanf("%d",&n);
        if(n==1)
          {
            puts("0");
            continue;
          //如果x^1，那么不需要操作
          }
        if(n==0)
          return 0;
          //结束
        for(floor=0;1;floor++)//关键语句：枚举边界
          {
            if(dfs(0,1))
            {
                printf("%d\n",floor);
                break;
            }
          }
    }
}