4406. 积木画
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;//模
//方案数可能会爆int
long long dp[2][3];//dp[i][j]表示前i列填满且填了第i+1列j个位置的方案
int main(){
int n;
cin >> n;
//三种方块 填满一共有三种方案
//1. I型方块竖着放 填满第i列 i+1列为空
dp[1][0] = 1;
//2 两个L型方块 填满第i列 i+1列填了一个
dp[1][1] = 2;//因为方块可以自由旋转 所以共有两种可能
//3. 两个I型方块横放 第i列 i+1列都被填满
dp[1][2] = 1;
for (int i = 2; i <= n; i++){//第一列状态方程已经写好 从第二列开始遍历
//由于状态转移过程中第i列的状态由 第i-1列转移 所以所有的状态可以由i-1 & 1 和 i & 1 轮流转换
//I型方块竖放能填满的情况有: 1. i - 1列也I型竖放填满 2. i - 1列由两个I型方块横放
dp[i & 1][0] = (dp[i - 1 & 1][0] + dp[i - 1 & 1][2]) % mod;
//L型方块合法: i-1列为竖放,这样的话第i列的L型方块无论是正放还是倒放都是合法的
//i-1列为一个L型方块
dp[i & 1][1] = (dp[i - 1 & 1][0] * 2 + dp[i - 1 & 1][1]) % mod;
//I型方块横放合法状态:1.第i-1列是竖放的I型 2.第i-1列是一个L型方块摆成的7或镜像L
dp[i & 1][2] = (dp[i - 1 & 1][0] + dp[i - 1 & 1][1]) % mod;
}
cout << dp[n & 1][0];//第n列没有方块伸出来的状态和即为答案
return 0;
}