问题1071--彩带

1071: 彩带

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

题目描述

南康中学80周年校庆，小林准备用一些白色、蓝色和红色的彩带来装饰学校食堂的橱窗，他希望满足以下两个条件：
(1) 相同颜色的彩带不能放在相邻的位置；
(2) 一条蓝色的彩带必须放在一条白色的彩带和一条红色的彩带中间。

    现在，他想知道满足要求的放置彩带的方案数有多少种。例如，如下图所示为橱窗宽度n=3 的所有放置方案，共 4种。

 

输入

一行一个整数n，表示橱窗宽度(或者说彩带数目)。

输出

一行一个整数，表示装饰橱窗的彩带放置方案数。

样例输入 Copy 

3

样例输出 Copy 

4

提示

对30%的数据满足：1≤n≤15。
对100%的数据满足：1≤n≤45。

来源/分类

递推算法 
[提交] [状态]