您当前位置：首页 > php开源 > php教程 > UVA - 1374 Power Calculus 迭代深搜

UVA - 1374 Power Calculus 迭代深搜

来源：程序员人生发布时间：2015-06-08 08:12:15 阅读次数：2501次

题目大意：问从1变到n最少需要多少步。变换规则以下
1.变化进程中的中间结果可以任意使用
2.每次只能挑选两个数进行加减

解题思路：先算1下最少需要多少步，然后在如果在当前步数下没法到达结果的话，就当前步数加1，继续搜索下去

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1010
int num[maxn], cnt, n ,MIN_depth;

bool dfs(int cur, int depth) {

    if(depth >= MIN_depth) {
        if(cur == n)
            return true;
        return false;
    }
    int MAX = 0;
    for(int i = 0; i < cnt; i++)
        MAX = max(MAX,num[i]);
    if( ((cur + MAX) << (MIN_depth - depth - 1)) < n)
        return false;

    for(int i = cnt - 1; i >= 0; i--) {
        num[cnt++] = cur + num[i];
        if(dfs(cur + num[i], depth+1))
            return true;
        cnt--;
        num[cnt++] = cur - num[i];
        if(dfs(cur - num[i],depth+1))
            return true;
        cnt--;
    }
    return false;
}

int main() {
    while(scanf("%d", &n) == 1 && n) {

        MIN_depth = 0;
        int t = 1;
        while(t < n) {
            t += t;
            MIN_depth++;
        }

        while(1) {
            num[0] = cnt = 1;
            if(dfs(1,0))
                break;
            MIN_depth++;
        }
        printf("%d
", MIN_depth);
    }
    return 0;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 [置顶] iOS 导入shareSDK包，但是却提示找不到头文件 ShareSDK/ShareSDK.h file not found

下一篇 Java处理正则表达式特殊字符转义

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点