P8784 [蓝桥杯 2022 省 B] 积木画 题解

· · 题解

题目传送门

1.分析：

这道题是一道 dp 题，n 的范围高达 10^7，所以时间复杂度只有一种：O(n)。

我们可以这样想，一个积木放上去后，可能会出现三种情况：第一行比第二行多出一个积木；两行积木数相等；第二行比第一行多出一个积木。

这时候有同学可能会问：为什么最多就多出一个积木呢？

因为最后的答案一定是两行积木数相等，如果两行差的多了，就不能用 L 型积木填补。只用 I 型积木填补的话，只能横着填补，我们完全可以在之前相差不超过 1 时就用 I 型积木横着填补。

所以，状态定义就是：int f[10000005][3]。注意：这里的 f[i][0] 和 f[i][2] 表示更长的一列的长度为 i。

接下来就是动态转移方程了。

如果第一行比第二行多出一个积木，也就是状态 f[i][0]。此时我们可以用一个 I 型积木在第一行横向填补，这样在填补前第二行就会多出一个积木，也就是 f[i-1][2]；也可以用一个 L 型积木填补第 i 列和 i-1 列，这样填补前两行积木数就相等，也就是 f[i-2][1]。

如果第二行比第一行多出一个积木，也就是状态 f[i][2]。此时与上一种情况类似，也是两种方案，分别是用一个 I 型积木在第二行横向填补和用一个 L 型积木进行填补。分别是 f[i-1][0] 和 f[i-2][1]。

最后，也是最复杂的一种情况，就是两行积木数相等，即状态 f[i][1]。此时有 4 种情况。我们可以用两个 I 型积木横向填补第 i 列和第 i-1 列，就是 f[i-2][1]；可以用一个 I 型积木纵向填补第 i 列，也就是 f[i-1][1]；可以用一个 L 型积木填补第 i 列和第 i-1 列的第一行，也就是 f[i-1][2]；还可以用一个 L 型积木填补第 i 列和第 i-1 列的第二行，也就是 f[i-1][0]。

温馨提示：这一部分可能不是很好懂，同学们可以画个图帮助理解。

初始化就很简单了，即一列都没有，两行积木数都为 0 也就是积木数相等的情况有 1 种，也就是 f[0][1]=1。

输出也很简单，就是前 n 列，两行积木数相等的情况数。

2.AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,f[10000005][3];
int main(){
    cin>>n;
    f[0][1]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=(f[i-2][1]+f[i-1][2])%mod;
        f[i][1]=((f[i-2][1]+f[i-1][1])%mod+(f[i-1][0]+f[i-1][2])%mod)%mod;//两两相加就取模，防止超出int
        f[i][2]=(f[i-2][1]+f[i-1][0])%mod;
    }
    cout<<f[n][1];
    return 0;
}