poj 2248 Addition Chains （迭代加深搜索）

【题目描述】

	An addition chain for n is an integer sequence with the following four properties:

a0 = 1

am = n

a0 < a1 < a2 < ... < am-1 < am

For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=k-1) with ak=ai+aj

	You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.

【题目链接】

Addition Chains

【算法】

枚举构造答案,迭代加深搜索。

剪枝：

1、从大到小枚举i，j

2、排除冗余（判重）

【代码】

#include <stdio.h>

#include <cstring>

using namespace std;

int n,deep;

int ans[1000],v[1000];

bool dfs(int cur) {

    if(cur>deep) {

        if(ans[deep]==n) return 1;

        return 0;

    }

    for(int i=cur-1;i>=0;i--) {

        for(int j=i;j>=0;j--) {

            if(ans[i]+ans[j]<=n&&!v[ans[i]+ans[j]]) {

                ans[cur]=ans[i]+ans[j]; v[ans[i]+ans[j]]=1;

                if(dfs(cur+1)) return 1;

                v[ans[i]+ans[j]]=0;

            }else if(ans[i]+ans[j]<=ans[cur-1]) break;

        }

    }

    return 0;

}

int main() {

    while(~scanf("%d",&n)&&n) {

        printf("1"); ans[0]=1;

        if(n==1) { puts(""); continue; }

        for(deep=1;!dfs(1);deep++) memset(v,0,sizeof(v));

        for(int i=1;i<=deep;i++) printf(" %d",ans[i]);

        puts("");

    }

    return 0;

}

巴特西

poj 2248 Addition Chains （迭代加深搜索）

【题目描述】

【题目链接】

【算法】

【代码】

最新文章

热门文章