题目简述

www.luogu.com.cn

题目思路

这道题是很经典的动态规划题，最重要的是得出状态转移方程。

划分阶段

设定两个数组 fN,gNf_{N}, g_{N}，分别表示填满前 2×i2 \times i 格子的方案数以及填满前 i×2+1i \times 2+1 格子的方案数。

答案即为 fnf_{n}。

状态转移方程

1×21 \times 2的瓷砖的摆放方式有两种：横着摆和竖着摆。

因此第一种瓷砖的状态转移方程为：

fi=fi−1+fi−2f_{i} = f_{i - 1} + f_{i - 2}

由于L型瓷砖可以进行旋转摆放，故一共有3种可能：

  • 通过两个L型瓷砖互补摆完。

  • 仅在1×21\times 2的瓷砖后继续摆放。

故第二种瓷砖的状态转移方程为：

gi=gi−1+fi−1g_{i} = g_{i - 1} + f_{i - 1}

综上所述

状态转移方程为：

fn=fn−1+fn−2+2×gn−2f_{n} = f_{n - 1} + f_{n - 2} + 2 \times g_{n - 2}

初始化

f0=1,g0=0,f1=g1=1f_{0} = 1, g_{0} = 0, f_{1} = g_{1} = 1

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 9;
const int mod = 1e4;

int f[N], g[N];

int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        f[i] = ((f[i - 1] + f[i - 2]) % mod + 2 * g[i - 2] % mod) % mod;
        g[i] = (g[i - 1] + f[i - 1]) % mod;
    }
    cout << f[n] << '\n';
    return 0;
}