首页 > 其他 > 详细

[題解](迭代加深)POJ2248_Addition Chains

时间:2019-06-01 00:22:54      阅读:157      评论:0      收藏:0      [点我收藏+]

發現m不會特別大,也就是層數比較淺,所以採用迭代加深

由於xi+xj可能相同,所以開一下vis數組判斷重複

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10009;
int n,x[maxn],ceil;
bool c[109];
bool dfs(int dep,int now){
    if(dep>ceil)return x[ceil]==n;
    for(int i=now-1;i>=1;i--){
        for(int j=i;j>=1;j--){//必須從i開始 
            if(x[i]+x[j]<=x[now-1])break;
            if(c[x[i]+x[j]])continue;
            x[now]=x[i]+x[j];
            if(dfs(dep+1,now+1))return 1;
        }
    }return 0;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        ceil=1;
        memset(x,0,sizeof(x));
        memset(c,0,sizeof(c));
        x[1]=1;
        while(!dfs(2,2))ceil++;
        for(int i=1;i<=ceil;i++)printf("%d ",x[i]);
        printf("\n");
    }
}

 

[題解](迭代加深)POJ2248_Addition Chains

原文:https://www.cnblogs.com/superminivan/p/10958016.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!