LOJ10021 Addition Chains

题目描述

原题来自：ZOJ 1937

已知一个数列 A0,A1,A2,A3,...,Am（其中A0=1,Am=n,A0<A1<A2<A3<...<Am ）。对于每个 k，需要满足 Ak=Ai+Aj（0<=i，j<k这里 i 与 j 可以相等）。

现给定 n 的值，要求 m 的最小值（并不要求输出），及这个数列每一项的值（可能存在多个数列，只输出任一个满足条件的就可以了）。

输入格式

多组数据，每行给定一个正整数 n 。

输入以 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,1<=k<=m

________________________

深搜，就是填一个表格，要求每个值是前面两个值的和，要求表格最短。

要求最短当然从大到小加，其他的就是普通搜索！

_________________________

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,ans;

 4 int sz[105],da[105];

 5 void dfs(int p)

 6 {

 7     if(sz[p-1]>n)return;

 8     if(p-1>=ans)return ;

 9     if(sz[p-1]==n && p-1<ans)

10     {

11         ans=p-1;

12         for(int i=1;i<p;++i)da[i]=sz[i];

13     }

14     for(int i=p-1;i>=1;--i)

15     {

16         sz[p]=sz[p-1]+sz[i];

17         dfs(p+1);

18     }

19 }

20 int main()

21 {

22     sz[1]=1;

23     while(scanf("%d",&n)==1 && n)

24     {

25         ans=105;

26         dfs(2);

27         for(int i=1;i<=ans;++i)printf("%d ",da[i]);

28         putchar('\n');

29     }

30     return 0;

31 }

巴特西

LOJ10021 Addition Chains

最新文章

热门文章