构造数列

[题目描述]

请构造一个尽量短的序列 A，长度为 len，一开始会给你一个正整数 n，

满足以下条件：

A[1]=1

A[len]=n

A[i]>A[i-1] （len>=i>=2）

A[x]=A[i]+A[j] （1<=i，j<x）

[输入文件]

此题有多组数据，每行一个正整数 n，

输入以 0 结尾

[输出文件]

每行 len 个正整数，为 A 序列

[输入样例 1] 

4 

0

[输出样例 1]

1 2 4

[输入样例 2] 

5 

77 

0

[输出样例 2]

1 2 3 5

1 2 4 5 9 18 36 41 77

[数据范围]

30%： n<=10

100%： n<=100

100%： 数据组数不超过 10 组

 

---

　　分析：

　　今天上午考试的时候全程状态掉线，这道题的思路都没想到。

　　首先很明显可以先确定搜索的深度，因为最快搜到一个数的方法就是不断乘以2，那么搜索深度的下界就是$log(n)$，那么就在这个深度的基础上进行搜索。然后加两个剪枝：当前得到的数$a[x]$大于$n$就直接退出；当前得到的数最终可能到达的最大的数也小于$n$就直接跳过。

　　Code：

 

//It is made by HolseLee on 20th July 2018#include
     
      using namespace std;int n,a[11],depth;bool flag;inline void dfs(int now){    if(flag)return;    if(now==depth+1){        if(a[now-1]==n)flag=true;        return;}    for(int i=1;i
      
       a[now-1]&&a[i]+a[j]<=n){            int num=a[i]+a[j];            for(int k=now;k
       
        >n;if(!n)break;        memset(a,0,sizeof(a));        depth=1;a[1]=1;int now=1;        while(now