信息学奥赛一本通T1443：Addition Chains

【题目描述】

已知一个数列a0,a1……am，其中a0=1,am=n; a0<a1<a2<……<am−1<am。对于每个k(1≤k≤m)满足ak=ai+aj(0≤i,j≤k−1),这里i与j可以相等。

现给定n的值，要求m的最小值（并不要求输出）及这个数列的值（可能存在多个数列，只输出任意一个满足条件的就可以）。

【输入】

多组数据，每行给定一个正整数n。输入以0结束。

【输出】

对于每组数据，输出满足条件的长度最小的数列。

【输入样例】

5
7
12
15
77
0

【输出样例】

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int n;
int a[N];
bool vis[N];
int cnt;
bool dfs(int step){
    if(step>cnt){
        if(a[cnt]==n)
            return true;
        return false;
    }

    for(int i=step-1;i>=1;i--){//搜索顺序优化
        for(int j=i;j>=1;j--){
            int temp=a[i]+a[j];
            if(temp>n)//可行性剪枝
                continue;
            if(!vis[temp]){
                if(temp<=a[step-1])
                    return false;

                vis[temp]=true;
                a[step]=temp;
                if(dfs(step+1))
                    return true;
                vis[temp]=false;
            }
        }
    }
}
int main(){
    while(scanf("%d",&n)!=EOF&&n){
        memset(a,0,sizeof(a));

        if(n==1)
            printf("1\n");
        else if(n==2)
            printf("1 2\n");
        else{
            a[1]=1;
            a[2]=2;
            cnt=3;
            while(!dfs(3)){
                memset(vis,false,sizeof(vis));
                cnt++;
            }
            for(int i=1;i<=cnt;i++)
                printf("%d ",a[i]);
            printf("\n");
        }
    }
    return 0;
}

信息学奥赛一本通T1443：深搜的剪枝技巧 Addition Chains 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 Addition Chains