Addition Chains

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1094 字

迭代加深 DFS，优先翻倍逼近目标值

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1443
// 题意：给定 n，求最短的加法链 a_0 = 1 < a_1 < ... < a_m = n，且每项都是前面某两项（可相同）之和，输出这个数列。
// 思路：迭代加深 DFS。
// 1. 从长度 m = 1 起逐步加深，第一次找到解就是最短的。
// 2. 每一层从大到小枚举 a_i + a_j，优先尝试翻倍，能快速逼近 n。
// 3. 剪枝：即使后面每一项都翻倍也达不到 n 就直接回溯。
// 复杂度：指数级搜索，深度一般不超过 15，剪枝后很快
// 易错点：新项必须严格大于前一项，等于或小于都不合法，枚举时要跳过。
// 易错点：剪枝里「后面全翻倍」的上界要用循环乘 2 计算，直接左移会溢出。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[64];
bool dfs(int k){
    if(k == m) return a[k] == n;
    long long cap = a[k];
    for(int i = 0; i < m - k && cap < n; i++) cap *= 2;
    if(cap < n) return false;
    for(int i = k; i >= 0; i--){
        for(int j = i; j >= 0; j--){
            int v = a[i] + a[j];
            if(v <= a[k] || v > n) continue;
            a[k + 1] = v;
            if(dfs(k + 1)) return true;
        }
    }
    return false;
}
int main(){
    while(cin >> n && n){
        a[0] = 1;
        for(m = 0; ; m++){
            if(dfs(0)) break;
        }
        for(int i = 0; i <= m; i++){
            if(i) cout << " ";
            cout << a[i];
        }
        cout << "\n";
    }
    return 0;
}

Addition Chains

正文

一本通·提高篇的其它内容