3923铺瓷砖。（cover）

3923   铺瓷砖。（cover）

题目描述

用红色的1×1和黑色的2×2两种规格的瓷砖不重叠的铺满n×3的路面，求出有多少种不同的铺设方案。

输入格式:

一行一个整数n，0<n<1000。

输出格式:

一行一个整数，为铺设方案的数量模12345的结果。
输入样例 复制 
2
输出样例 复制 
3

说明

用f（n）表示n×3的路面有多少种不同的铺设方案。把路面看成n行3列，则问题可以分成两种情况考虑，一种是最后一行用3块1×1的瓷砖铺设；另一种是最后两行用2块2×2和2块1×1的瓷砖铺设（最后两行就有两种铺设），第一种铺法就转换为f（i-1）的问题了，第二种铺法就转换为f（i-2）的问题了。根据加法原理，得到的递推关系式为f（i）=f（i-1）+f（i-2）×2，边界为f（0）=0，f（1）=1；
10
16
通过提交
时空限制1000ms/64mb
题目来源
评测方式在线评测
题目类型递推
难        度