特别鸣谢

1、感谢 @wty 指出了网页链接在某些情况下可能会挂掉的问题

题目描述

满足如下条件的序列 $X$（序列中元素被标号为 $1、2、3…m$ ）被称为“加成序列”：

$1、X[1]=1$

$2、X[m]=n$

$3、X[1]<X[2]<…<X[m-1]<X[m]$

$4、对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得X[k]=X[i]+X[j]。$

你的任务是：给定一个整数 $n$，找出符合上述条件的长度 $m$ 最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

输入样例

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

算法1

(普通的迭代加深)

其实本题目比较大众化，$n$ 只有100

(其实如果我来出题我不会这么便宜你们的)

我们发现，最优情况下 $log100$ 是7到8的范围，但绝对答案层不止这点

可就算是放宽了算，乘3也只有30左右

深度很浅，很容易想到迭代加深

(期待的TLE没有出现)

接下来该我表演了

算法2

(我的迭代加深其实就是一个小小的ida*)

我们知道，每次选最大的就可以使序列最短

那就选最后出现的啊

没错，每次就乘一个2，那就是左移一个$2^{d-u+1}$

你以为这样就完了吗？

不可能的！

可以发现，我们当前的数是可以被最后一个数加上其他数组成的。而且如果太小了，对答案也是没有贡献的。所以，又优化了时间复杂度！说实话这个优化是我手滑写错代码偶然发现的QwQ

你以为这样就完了吗？

真的完了 （本蒟蒻想不出来了）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int NN=104;
int sum[NN],n;
bool st[NN];
bool dfs(int u,int d)
{
    if(u==d+1)
    {
        if(sum[d]==n)
        {
            for(int i=1;i<=d;i++)
                printf("%d ",sum[i]);
            puts("");
            return true;
        }
        else
            return false;
    }
    if((sum[u-1]<<(d-u+1))<n)//精髓！
        return false;
    if(u>d)
        return false;
    for(int j=u-1;j>0;j--)//精髓！
        if(!st[sum[u-1]+sum[j]])
        {
            sum[u]=sum[u-1]+sum[j];
            st[sum[u]]=true;
            if(dfs(u+1,d))
            {
                st[sum[u]]=false;
                return true;
            }
            st[sum[u]]=false;
        }
    return false;
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        int d=1;
        sum[1]=1;
        while(!dfs(2,d))
            d++;
    }
    return 0;
}

优化代码
https://www.acwing.com/problem/content/submission/code_detail/1666796/
无优化代码
https://www.acwing.com/problem/content/submission/code_detail/4145080/
优化了一半的时间,数据大点可以保证不tle
我试了一下，算法二可以1000000都不tle(当然，不能保证，但100000是妥妥的)

到了最后了，本蒟蒻写一篇题解也不容易，希望各位大佬点一下那个向上的三角支持我一下，谢谢！