AcWing 4406. 积木画
原题链接
中等
作者:
逸误
,
2024-04-05 15:17:36
,
所有人可见
,
阅读 6
//dp思路:f[i][j]:表示已经塞满前i-1列(现在操作第i列),且第i列的状态为j的所有方案的集合
//一定要注意不能有重复计数!
//10的时候加上一根竖的变成11,不可以和下一行00的时候加上一根竖的变成10重复!
//10 11 00 10
//因此要人为定义,这一步一定是只能在第i列操作(放置的方块的左边要在第i列)
#include <iostream>
using namespace std;
const int N = 1e7 + 5, MOD = 1e9 + 7;
int n;
int f[N][4];
int g[4][4]=
{
{1,1,1,1},//分别是在第i列放:一个|、一个L(反)、一个L、两个横
{0,0,1,1},//两个1分别是:一横,一个L
{0,1,0,1},//同上
{1,0,0,0}//i列已满,只有什么也不放这一种,就更新到下一列
};//状态转移矩阵!g[i][j]=1说明i状态在操作后,后一列可以变成j状态
int main()
{
cin>>n;
f[1][0]=1;
for(int i=1;i<=n;i++)//用前面的去更新后面的,而不是后面的找前面的状态更新
for(int j=0;j<4;j++)//这一列
for(int k=0;k<4;k++)//前一列
f[i+1][j]=(f[i+1][j]+f[i][k]*g[k][j])%MOD;
cout<<f[n+1][0]<<endl;
return 0;
}