大秦为您打开题目传送门（

3/1 题目大意

题目的表述十分清楚，他就是让你用竖着两个方块和 L 形的方块填满一个长 $n$，宽 $2$ 的长方形。方块可以旋转，如下图

1
2
3
4
  ___                             ___    方块2（反）* ______
 /__/\  方块1（横）* ______       /__/__             /__/__/\
/__/\/             /__/__/\     /__/__/\            \_/__/\/
\__\/ *方块1（竖）  \__\__\/     \__\__\/ *方块2（正）  \__\/    *此图大大滴形象

3/2 解题思路

我们一拿到这道题，读完以后，显而易见的，这是一个编程题递推题。那么一开始我们大都会像下面这样推

设 $dp[i]$ 表示铺满前 $i$ 列的方案数。
然后，自己枚举出 $dp[1]=1, dp[2]=2, dp[3]=5,dp[4]=11$ 。
之后呢，又推出 $\tt DP$ 方程是 $dp[i]=dp[i-1]+dp[i-2]+dp[i-3]\times 3+dp[i-4]\times 2$
然后一跑，发现，炸了！样例都没过，这是为什么呢

这题和其他铺砖类型题不太一样，为什么呢，其他的铺砖题都是一块砖可以铺满一列，不会有突出来的，但是，这道题的方块2会导致有一个突出来的方块情况，所以，我们要适当转变状态定义。

我们思考如何拼出一个平的东西呢？有两种情况，第一，我们可以用一个竖的方块1（下文简称 | ）和一个反的方块2（下文简称 7）
这对应的是 平+|=平 和 凸+7/L=平 两种情况

那么，还有吗，如果我们只是构造平的，肯定不可以，那第二种转移方式肯定就没有用了，所以我们要第三种转移方式，那就是：构造平/凸。也就是所谓的 平/凸+7/L=凸/平 这样，我们就可以继续推下去了

所以综上，我们可得转移方程为 $dp[i]=dp[i-1]\times 2+dp[i-3]$ 。

为什么是 $dp[i-3]$ 呢？因为这个转移其实是给 $i+1$ 使用的，我们不过是准备而已。

3/3 题目代码

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

int n;
int dp[1000010];

void Input() {
    scanf("%d", &n);
}

void Work() {
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;
    dp[4] = 11;
    for (int i = 5; i <= n; i++) { //其实从4就可以开始推了，我这边多写了一个
        dp[i] = dp[i - 1] * 2 + dp[i - 3];
        dp[i] %= 10000;
    }
    printf("%d", dp[n]);
}

int main() {
    Input();
    Work();
    return 0;
}

并不小声BB：这其实是我博客里第一个单讲题目的题解，，，