45 lines
1.7 KiB
C++
45 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int MOD = 10000;
|
||
const int N = 1000010;
|
||
int f[N][3];
|
||
|
||
// 功能：从后向前考查，保证填充满的情况下，计算在第x列，放了count个小方块情况下，有多少种办法
|
||
// 参数x:当前考查的是第x列
|
||
// 参数count:在x列放了几个位置，范围是 0个与1个
|
||
int dfs(int x, int count) {
|
||
if (f[x][count] >= 0) return f[x][count];
|
||
|
||
if (x == 0) {
|
||
//第0列，而且还放了一个，这种情况是不可能发生的，所以方案数为0
|
||
if (count == 1) return 0;
|
||
//第0列，个数为0，是正确的，是有返回递归终点值的,值为1，
|
||
return 1;
|
||
}
|
||
//出现了不可能发生的负值情况，返回0
|
||
if (x < 0) return 0;
|
||
//结果变量
|
||
int ans = 0;
|
||
//如果x列没有小方格被放下
|
||
//情况1：放一个竖的，前面的可能性就是 dfs(x-1,0)
|
||
//情况2：放两个横的，前面的可能性就是 dfs(x-2,0)
|
||
//情况3：放一个向左下开口的L，或者放一个向左上开口的L,都会造成前面的剩余中产生第x-1列是一个小方格被放下的情况产生，即dfs(x-1,1)
|
||
if (count == 0) ans = (ans + dfs(x - 1, 0) + dfs(x - 2, 0) + 2 * dfs(x - 1, 1)) % MOD;
|
||
|
||
//如果x列有一个小方格被放下
|
||
//情况1：用一个L可以搞定，就是 dfs(x-2,0)
|
||
//情况2：用横着的放进来，就会造成x-1列，出现一个小方格的情况，即 dfs(x-1,1)
|
||
if (count == 1) ans = (ans + dfs(x - 2, 0) + dfs(x - 1, 1)) % MOD;
|
||
return f[x][count] = ans;
|
||
}
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
for (int i = 0; i < N; i++)
|
||
for (int j = 0; j < 3; j++)
|
||
f[i][j] = -1;
|
||
|
||
cout << dfs(n, 0);
|
||
} |