这里来一个更优的解法

本题数据范围较大，为3s，512M，比较宽松。然而在更极端的环境下容易MLE，考虑压缩空间

参考到队长题解的代码，开出了一个 $g$ 数组，这里考虑压缩。

首先列举答案的可能，找找规律

i	答案
1
2
3	5
4	11
5	24
6	53
7	117
8	258
9	569
10	1255
$\cdots$

若取 $i = 5$ 我们可以知道 $I$ 型积木的可能有 $dp_{i-1} + dp_{i-2} = 16$ 种可能，离我们算出来的方案还差 $8$ 种可能，即 $L$ 型积木混合或单独组成的可能。而 $8$ 正是 $dp_{i-2} + dp_{i-3} + dp_{i-4}$ 的和。

同理可用数学归纳法推得该式成立，为此我们推出状态转移方程为

$$dp_i = (dp_{i-1}+dp_{i-2}) + (dp_{i-2}+dp_{i-3}+dp_{i-4}) $$

即

$$dp_i = dp_{i-1}+2dp_{i-2}+dp_{i-3}+dp_{i-4}$$

此外，我们需要对 $i < 4$ 的情况进行特判，为了使上式在 $i = 4$ 成立，我们使 $dp_0 = 0$，可得

$$dp_i = \begin{cases} 1, i = 0, 1 \\ 2, i = 2 \\ 5, i = 3 \\ dp_{i-1}+2dp_{i-2}+dp_{i-3}+dp_{i-4}, i \ge 4 \end{cases} $$

接下来递归求出即可，综上，空间占用相比队长题解少了一个长度为 $n + 1$ 的数组

代码参考实现如下

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    constexpr i64 mod = 1000000007;
    i64 n;
    cin >> n;
    vector dp(n + 3, 0ll);  // 开大点，避免小数据导致越界
    dp[0] = dp[1] = 1, dp[2] = 2, dp[3] = 5;
    if (n > 3)
        for (auto &&i: views::iota(4, n + 1))
            dp[i] = (((dp[i - 1] + (dp[i - 2] << 1) % mod) % mod + dp[i - 3]) % mod + dp[i - 4]) % mod;
    cout << dp[n];
    return 0;
}

【2022年省赛B组】试题G: 积木画

😄 题解

定义$f[n]$表示$2 \times n$的画布的方案数，对于$I$型积木而言，可以很容易推断出$f[n]$与$f[n - 1],f[n - 2]$有关。

1. 对于$2 \times (n - 1)$的画布的所有方案，在最后一列放一个$I$型积木即可，也就是$f[n]$的方案数包括$f[n - 1]$的方案数。
2. 同理，对于$2 \times (n - 2)$的画布的所有方案，在最后两列横放两个$I$型积木即可，也就是说$f[n]$的方案数包括$f[n - 2]$的方案数。
3. 对于$L$型积木呢？$L$型积木只有当前$n - 2$列填满，第$n - 1$列只有1个单位填满时，才可以放在最后面。

这里记前$n$列填满，第$n + 1$列填了一个单位时的方案数为$g[n]$。那么$f[n]$的递推式可以通过上面三种情况求得：

$$f[n] = f[n - 1] + f[n - 2] + g[n - 2]$$

然后考虑$g[n]$的推导：

1. 所有的$g[n - 1]$的情况后横放一个$I$型积木即可变成$g[n]$
2. 所有的$f[n - 1]$的情况后可以有两种方式放置$L$型积木，可以变成$g[n]$ 因此有:

$$g[n] = g[n - 1] + 2 \times f[n - 1]$$

同时维护$g, f$, 在实现时注意不断取余，防止运算溢出。

提交代码

#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;

void solve()
{
    int n; std::cin >> n;
    std::vector<int> f(n + 1), g(n + 1);

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

    for(int i = 2; i <= n; i++)
    {
        g[i] = (2 * f[i - 1] + g[i - 1]) % mod; 
        f[i] = (f[i - 1] + f[i - 2] + g[i - 2]) % mod;
    }
    std::cout << f[n] << "\n";
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1; 
    while(t--) solve();
    return 0;
}