UVA - 1374 Power Calculus 迭代深搜

发布时间：2020-12-13 20:43:03 所属栏目：PHP教程来源：网络整理

导读：题目大意：问从1变到n最少需要多少步。变换规则以下 1.变化进程中的中间结果可以任意使用 2.每次只能挑选两个数进行加减解题思路：先算1下最少需要多少步，然后在如果在当前步数下没法到达结果的话，就当前步数加1，继续搜索下去 #includecstdio #includecs

题目大意：问从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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!