2248:Addition Chains

keyword

探索　C++

概要

nに対するaddition chainとは次を満たす数列である。a_0 = 1, a_m = n, a_0 < a_1 < ... < a_m, a_k = a_i + a_j 0<=i,j < k。N(<100)が与えられるのでNに対するaddition chainに対して最も短いものを出力する問題。
問題文中に探索しろって書いてあったから探索した。答えが小さいので実際は埋め込みした。以下のソースは埋め込み用に使ったもの。計算量は謎。

int ns[100];
int tar, ans;
vector<int> as;

void dfs(int p){
    if(p >= ans) return;
    if(ns[p-1] == tar){
        if(p < ans){
            ans = p;
            as = vector<int>(ns,ns+p);
        }
        return ;
    }
    bool visited[101];
    for(int i=0; i<101;i++)visited[i] = false;
    for(int i=p-1; i>=0; i--){
        for(int j=i; j>=0; j--){
            int t = ns[i] + ns[j];
            if(t > ns[p-1] && t <= tar && !visited[t]){
                ns[p] = t;
                visited[t] = true;
                dfs(p+1);
            }
        }
    }
    return ;
}

void solve(int n){
    as.clear();
    ns[0] = 1;
    tar = n;
    ans = 1<<30;
    dfs(1);
    putchar('\"');
    for(int i=0; i<as.size(); i++){
        printf("%d%c",as[i],(i==as.size()-1)?'\"':' ');
    }
    putchar(',');
    putchar('\n');
}