问题 1224 --排列组合?贪心?

1224: 排列组合?贪心?

时间限制: 1 Sec  内存限制: 128 MB
提交: 58  解决: 11
[提交][状态][讨论版][命题人:]

题目描述

当一个串内容全部都为1时称作全1串,由于程序猿是无所不能的,所以作为程序猿的你可以合并任意相邻的两个1变成2,然后形成一个全新的串,如果给你一个新的全1串,你可以计算一下可以构成多少不同的串吗?

输入

多组输入,输入一个整数n,不超过2000,表示串长度

输出

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

样例输入

1
3
5

样例输出

1
3
8

提示

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

来源

 

[提交][状态]