hdu 5686 Problem B(斐波那契数)

Problem Description
  度熊面前有一个全是由1构成的字符串,被称为全1序列。你可以合并任意相邻的两个1,从而形成一个新的序列。对于给定的一个全1序列,请计算根据以上方法,可以构成多少种不同的序列。

 

Input
这里包括多组测试数据,每组测试数据包含一个正整数N,代表全1序列的长度。

1N200

 

Output
对于每组测试数据,输出一个整数,代表由题目中所给定的全1序列所能形成的新序列的数量。

 

Sample Input
1
3
5

 

Sample Output
1
3
8

Hint

如果序列是:(111)。可以构造出如下三个新序列:(111), (21), (12)。

根据题意,对于f[n]来说,如果不与之前的1合并那么就相当于在前面所有组成的序列后面加了个1而已。如果与第n-1个1合并那就相当于在前面n-2个1后面加上了个2而已。
所以就是斐波那契数了,因为数据比较大直接用Java艹过去了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注