这道题跟
P1990 覆盖墙壁很像,都是使用dp的方式:
我们可以使用这两个数组进行处理
f[i]表示覆盖了前i2个面积的墙壁,g[i]表示覆盖了前i2+1的面积
针对L形=>g数组(处理往前突),针对I形=>f数组
#include<iostream>
using namespace std;
const int N = 1e7+10,mod=1000000007;
int f[N],g[N];
int n;
int main(){
cin>>n;
f[0]=1;
g[1]=f[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]=(f[i-1]+g[i-1])%mod;
}
cout<<f[n];
return 0;
}