AcWing 4406. 与“蒙德里安的梦想”类似解法,附详细说明
原题链接
中等
作者:
路寻
,
2024-04-04 18:27:15
,
所有人可见
,
阅读 4
与“蒙德里安的梦想”类似解法,附详细说明
#include<iostream>
using namespace std;
const int N = 1e7+10;
const int mod = 1000000007;
int f[N][3];
int main(){
int n;cin>>n;
f[0][0] = 1;
for(int i = 1; i<=n; i++){
for(int j = 0; j<4; j++){
//1、当i-1列为0 1(1)时 ,表示i-1列第一行还没填充,如果用横向的长方形填充到i列 ,那么i列应为1 0(2)
//如果用L型填充第i列应变为 1 1(3),所以当j为2和3时,方案数要包括f[i-1][1]
//2、同理当i-1列为1 0(2)时 ,表示i-1列第二行还没填充,如果用横向的长方形填充到i列 ,那么i列应为0 1(1)
// 如果用L型填充第i列应变为 1 1(3),所以当j为1和3时,方案数要包括f[i-1][2]
//3、同理当i-1列为0 0(0)时 ,表i-1列示第一、二行还没填充,如果用二横向的长方形填充到i列 ,那么i列应为1 1(3)
// 如果用L型和翻转的L填充第i列应变为 1 0(2)或0 1(1),如果不延申到i列,
// 则可以用竖着的长方形填充i-1列,此时i列为0 0 (0),所以当j为0,1和2和3时,方案数要包括f[i-1][0]
//4、当i-1列为1,1(0)时,i列为0 0(0),所以当j为0时,方案数要包括f[i-1][3]
if(j == 0 )f[i][j] = (f[i-1][0]+f[i-1][3])% mod;
if(j == 1 )f[i][j] = (f[i-1][0]+f[i-1][2])% mod;
if(j == 2 )f[i][j] = (f[i-1][0]+f[i-1][1])% mod;
if(j == 3 )f[i][j] = ((f[i-1][0]+f[i-1][1])% mod+f[i-1][2])% mod;
}
}
cout<<f[n][0]<<endl;
return 0;
}