【POJ2248】Addition Chains

浅浅的花香味﹌ 2023-06-05 08:51 11阅读 0赞

### Description ###

给定整数n，构造一个递增的正整数序列使得a1=1,am=n,且对于任意的k（1≤k≤m）都存在ak=ai\+aj,最小化序列的长度（即最小化m）

### Solution ###

由于n规模较小，所以我们可以采用迭代加深搜索来求解答案，即固定搜索的深度（序列的长度），搜索答案，若搜索不到答案则加深深度。

于是我们设计搜索函数dfs(last, now)表示当前正在搜索now的位置，上一个位置的值为last，是否存在解。

那么搜索的出口很简单，当now大于限定的深度时，判断序列最后一个元素是不是n即可。

为了提高搜索效率，我们设计如下优化：

为了让答案尽快接近n，我们选择倒序枚举i，j（因为序列是单调上升的），并且当ai\+aj≤last时停止枚举即可。

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int n, dep, a[110];
     5 int dfs(int last, int now) {
     6     if (now > dep) {
     7         if (a[dep] == n) return 1;
     8         return 0;
     9     }
    10     for (register int i = now - 1; i >= 1; --i) {
    11         for (register int j = i; j >= 1; --j) {
    12             if (a[i] + a[j] > n) continue ;
    13             if (a[i] + a[j] <= last) break ;
    14             a[now] = a[i] + a[j];
    15             if (dfs(a[now], now + 1)) return 1;
    16         }
    17     }
    18     return 0;
    19 }
    20 int main() {
    21     while (scanf("%d", &n) && n) {
    22         a[1] = 1;
    23         for (dep = 1; ; dep++) {
    24             if (dfs(1, 2)) {
    25                 for (register int i = 1; i <= dep; ++i)
    26                     printf("%d ", a[i]);
    27                 puts("");
    28                 break ;
    29             }
    30         }
    31     }
    32     return 0;
    33 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11315559.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/734d65e74ddc44f888488ffbe606879e.png