题目描述
你有一个长为N
宽为2
的墙壁,给你两种砖头:一个长 2
宽1
,另一个是L
型覆盖3
个单元的砖头。如下图:
0 0
0 00
砖头可以旋转,两种砖头可以无限制提供。你的任务是计算用这两种来覆盖N×2
的墙壁的覆盖方法。例如一个 2×3
的墙可以有5
种覆盖方法,如下:
012 002 011 001 011
012 112 022 011 001
注意可以使用两种砖头混合起来覆盖,如 2×4
的墙可以这样覆盖:
0112
0012
给定N
,要求计算 2×N
的墙壁的覆盖方法。由于结果很大,所以只要求输出最后4
位。例如 2×13
的覆盖方法为 13465
,只需输出 3465
即可。如果答案少于 4
位,就直接输出就可以,不用加前导 0
,如 N=3
时输出 5
。
输入样例
13
输出样例
3465
算法1
(递推) $O(n^2)$
用f[i]
表示前i
列符合答案的数量
先考虑2x1
的格子
接下里考虑用L
型的
有以上两种摆法 用g[i]
表示前i-2
列摆好 L
型格子占第i
和i-1
列的集合
只能通过这两种方式转移过来g[i] = f[i - 1] + g[i - 1]
再对f[i]
进行考虑:f[i] = f[i - 1] + f[i - 2] + 2 * g[i - 2]
(因为L
型有两种摆法)
时间复杂度 $O(n)$
参考文献
C++ 代码
//二号砖头的数量一定是偶数个
#include <iostream>
using namespace std;
const int N = 1000010, mod = 10000;
int f[N], g[N];
int n;
int main()
{
cin >> n;
//g[n - 1] = f[n - 2] + g[n - 2];
//f[n] = f[n - 1] + f[n - 2] + 2 * g[n - 2]
f[0] = f[1] = 1;
g[1] = 1;
for(int i = 2;i <= n; i++)
{
g[i] = (g[i - 1] + f[i - 1]) % mod;
f[i] = (f[i - 1] + f[i - 2] + 2 * g[i - 2]) % mod;
}
cout << f[n] % mod << endl;
return 0;
}