2022蓝桥杯 G.积木画（优化到一维）

我们用$f[i]$表示将面积为$2\times i$的画布铺满的方案数，首先，当铺满了前$2\times (i-1)$的画布时第$i$块布只能摆放一个$I$型积木，故$f[i-1]$对$f[i]$的贡献为$f[i-1]$；而当铺满了前$2\times (i-2)$的画布时可以竖放两个$I$型积木或横放两个$I$型积木，但竖放两个$I$型积木就会重复计算一次$f[i-1]$，故$f[i-2]$对$f[i]$的贡献为$f[i-2]$；再来考虑其他情况：显然$L$型积木可以使用的数量只能为偶数，且第$i$（$i$为偶数）个$L$型积木与第$i+1$个之间一定是相匹配的，通过画图可以发现两个相匹配的L型积木之间只能摆放$x$个横向$I$型积木（$x$与两个$L$型积木之间的距离有关），而两个相匹配的$L$型积木只有两种摆法，因此可以得出递推式：$f[i]=f[i-1]+f[i-2]+2\times \sum _{j=0}^{j-3}f[j]$，用前缀和可以优化到$O(n)$
$代码如下：$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 1e7 + 5, mod = 1e9 + 7;
int n;
ll f[N], s[N];
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n; f[0] = s[0] = 1;
	for(int i = 1; i <= n; i++) {
		f[i] = (f[i] + f[i - 1] + f[i - 2]) % mod;
		if(i >= 3) f[i] = (f[i] + s[i - 3] * 2) % mod;
		s[i] = (s[i - 1] + f[i]) % mod;
	}
	cout << f[n];
	return 0;
}