第十三届蓝桥杯C++ B组 试题 G: 积木画

【问题描述】
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2
个单位面积）和 L 型（大小为 3 个单位面积）：

同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构
成。

小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？
积木可以任意旋转，且画布的方向固定。

【输入格式】
输入一个整数 N，表示画布大小。

【输出格式】
输出一个整数表示答案。

由于答案可能很大，所以输出其对 1000000007 取
模后的值
【样例输入】
3
【样例输出】
5

#include

using namespace std;
const int mod=1000000007;
/*
为了便于理解，我们不妨把2*n的矩阵转过来，即为n*2，每次竖着向下放积木。


对于每一层，2个格子一共只有4种摆放情况。


我们用0表示空，1表示已摆放积木。


（1）0 0,这一行为空,我们用数字0表示
（2）0 1,第一个空，第二个已经放置,我们用数字1表示
（3）1 0,第一个已放置，第二个为空,我们用数字2表示
（4）1 1,此行已满,我们用数字3表示
f[i][j]:第j行的摆放状态为i时，摆放数量。


 */
long long f[4][2];//因为空间较大，我们用滚动数组。


//（求第i行时，我们都只用到了第i-1行，也就是我们始终只用到了2行的信息）。


int main(){
	
	int n;
	cin>>n;
	f[3][0]=1;//这个初始化很重要！我们默认一来什么也没放是一种方法。


	//为什么不直接f[0][1]=1,因为我们为了统一下面的第一个dp转移。


	for(int i=1;i<=n;i++){
		//这一行为空，和上一行满了，是同一种情况。


		f[0][i%2]=f[3][(i-1)%2];
		//让第二个有摆放，可以通过2个块和3个块的形成。


		//摆放应该保证有“空间”，所以应该找到满足的第i-1行状态，方式相加即可。


		f[1][i%2]=f[2][(i-1)%2]+f[0][(i-1)%2];
		//下面两种同理，读者可以根据转移方程，自行画图理解！
		f[2][i%2]=f[1][(i-1)%2]+f[0][(i-1)%2];
		f[3][i%2]=f[3][(i-1)%2]+f[1][(i-1)%2]+f[2][(i-1)%2]+f[0][(i-1)%2];
		//mod
		for(int j=0;j<4;j++)
			f[j][i%2]=f[j][i%2]%mod;
	}
	cout<<f[3][n%2];//最终状态肯定是最后一行刚好放满
	return 0;
}