【poj3134】Power Calculus

2015.04.16 13:47 Thu | 11次阅读 | 旧日oi | 固定链接 | 源码

题意
求x经过至少几次乘法或除法,能达到x^n,其中乘法和除法都必须在已经求出来的数中进行
题解
迭代加深搜索,第一次写。
枚举深度,用深搜在深度范围内寻找答案,如果找不到,增加深度。

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,dep;
int a[maxn];
bool dfs(int cnt,int maxx)
{
    if(a[cnt]==n) return 1;
    if(cnt>=dep) return 0;
    if(maxx>n&&a[cnt]>n) return 0;
    maxx=max(maxx,a[cnt]);
    if(maxx*(1<<(dep-cnt))<n) return 0;
    for(int i=cnt;i>=0;i--)
    {
        a[cnt+1]=a[cnt]+a[i];
        if(dfs(cnt+1,maxx)) return 1;
    }
    for(int i=0;i<=cnt;i++)
    {
        a[cnt+1]=abs(a[cnt]-a[i]);
        if(dfs(cnt+1,maxx)) return 1;
    }
    return 0;
}
void work()
{
    if(n==1)
    {
        puts("0");
        return;
    }
    a[0]=1;
    for(dep=1;;dep++)
    if(dfs(0,1))
    {
        printf("%d\n",dep);
        return;
    }
}
int main()
{
    while(cin>>n&&n) work();
    return 0;
}```