题目描述 Description

从m开始，我们只需要6次运算就可以计算出m31：

m2=m×m，m4=m2×m2，m8=m4×m4，m16=m8×m8，m32=m16×m16，m31=m32÷m。

请你找出从m开始，计算mn的最少运算次数。在运算的每一步，都应该是m的正整数次方，换句话说，类似m-3是不允许出现的。

输入描述 Input Description

输入为一个正整数n

输出描述 Output Description

输出为一个整数，为从m开始，计算mn的最少运算次数。

样例输入 Sample Input

样例1
1

样例2
31

样例3
70

样例输出 Sample Output

样例1
0

样例2
6

样例3
8

数据范围及提示 Data Size & Hint

n（1<=n<=1000）

数据没有问题，已经出现过的n次方可以直接调用

/*迭代加深搜：论写好剪枝的重要性*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#define M 3010

using namespace std;

int vis[M],q[M],len,n,flag;

void dfs(int x,int t,int limit)

{

    if(x*pow(,limit-t)<n)return;//加了一堆剪枝，都不如这一个好用

    if(flag)return;

    if(x==n){flag=;return;}

    if(t==limit)return;

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

    {

        if(x-q[i]>=n&&!vis[x-q[i]])

        {

            q[++len]=x-q[i];vis[x-q[i]]=;

            dfs(x-q[i],t+,limit);

            --len;vis[x-q[i]]=;

        }

        if(x+q[i]<*n&&!vis[x+q[i]])

        {

            q[++len]=x+q[i];vis[x+q[i]]=;

            dfs(x+q[i],t+,limit);

            --len;vis[x+q[i]]=;

        }

    }

}

int main()

{

    scanf("%d",&n);

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

    {

        len=;memset(vis,,sizeof(vis));

        vis[]=;q[++len]=;

        dfs(,,i);

        if(flag)

        {

            printf("%d",i);

            return ;

        }

    }

    return ;

}