洛谷题单指南-递推与递归-P1990 覆盖墙壁

原题链接：https://www.luogu.com.cn/problem/P1990

题意解读：用两种可旋转的形状铺满N*2的区域，求方案数，可以使用递推。

解题思路：

步骤1、设f[i]表示铺满i*2的区域的方案数

根据要求，i*2区域最后一列有4种可能的铺法：

如果采用图1铺法，则有f[i] = f[i - 1]

如果采用图2铺法，则有f[i] = f[i - 2]

如果采用图3、图4铺法，由于第i-1列有空隙，无法仅使用f[]实现递推！

因此。。。

步骤2、另设g[i]表示铺满i*2的区域且第i列有一个空白的方案数

最后一列可能的情况：

以图1为例来讨论，最后一列可能的铺设方式有

如果采用图1铺法，则有g[i] = g[i - 1]

如果采用图2铺法，则有g[i] = f[i - 2]

因此，g[i] = g[i - 1] + f[i - 2]

步骤3、再来讨论步骤1中图3、图4的铺法

对于图3、图4，都有有f[i] = g[i - 1]

因此，f[i] = f[i - 1] + f[i - 2] + g[i - 1] * 2

步骤4：初始化

f[1] = 1, f[2] = 2

g[1] = 0, g[2] = 1

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int f[N], g[N], n;

int main()
{
    cin >> n;

    f[1] = 1;
    f[2] = 2;
    g[1] = 0;
    g[2] = 1;
    if(n <= 2) 
    {
        cout << f[n];
        return 0;
    }
    for(int i = 3; i <= n; i++)
    {
        f[i] = (f[i - 1] + f[i - 2] + g[i - 1] * 2) % 10000;
        g[i] = (g[i - 1] + f[i - 2]) % 10000;
    }
    cout << f[n];

    return 0;
}