题意：

一个与 nn 有关的整数加成序列 $<a_0,a_1,a_2,...,a_m>$ 满足以下四个条件：

1.$a_0=1$

2.$a_m=n$

3.$a_0<a_1<a_2<...<a_{m-1}<a_m$

4. 对于每一个 k(1≤k≤m) 都存在有两个整数 i 和 j(0≤i,j≤k-1,i和 j 可以相等 ) ，使得 $a_k=a_i+a_j$​

你的任务是：给定一个整数 nn ,找出符合上述四个条件的长度最小的整数加成序列。

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

举个例子，序列<1,2,3,5> 和 <1,2,4,5> 均为 n=5 时的解。

 

一看就是搜索，于是爆搜。。。

然而，这是个迭代加深搜索。。。

剪枝如下：

1.优化搜索顺序

显然倒序枚举更有可能得到可行解。

让数大一些，尽可能接近n；

2.排除不可行解

我们发现，对于加成数列的要求还有一个，即 $a_m=n$

假设当前已经通过枚举得出了 $a_i$ ，正准备搜索第 i+1 个数。

考虑通过当前形势下到第 m 项可以得到的最大值，显然，$max(a_{i+1})=a_i+a_i=2×a_i$​

$max(a_{i+2})=a_{i+1}+a_{i+1}=2×a_{i+1}=4×a_i=2^2×a_i$​

故由递推可得

$max(a_m)=2^{m-i}×a_i$​

所以在进行对 i+1 个数的搜索前，计算一下 $max(a_m)$ 是否可以达到 n ，

如果达不到则无需进行下一步的搜索。

 

#include
     
      #include
      
       using namespace std;#define love_nmr 0int n;bool flag;int ans[10050];int maxx;inline void print(){    for(int i=1;i
       
        =pos;i--)    {        for(int j=i;j>=1;j--)        {           int f=ans[depth]=ans[i]+ans[j];           for(int is=pos+1;is<=maxx;is++) f<<=1;           if(f