题目描述
积木画
样例
略
算法1
(状态压缩DP)
与蒙德里安的梦想一样,通过二进制表示状态进行压缩。与之不同的是,这个画布有两列,那么就存在4种状态,那么状态转移就直接用4*4的矩阵就可以数出来,蒙德里安有2^n状态需要枚举。
在表达状态转移矩阵的时候,i-1列已经填满,i列的状态有00、10、01、11四种,对应的i+1列的状态j有 (00,10、11、01)、(11、01)、(11、10)、(00)转化为十进制存储即构成矩阵。
状态转移矩阵构造完成,就可以初始化全都是竖着放的,那么f[0][0]=1,后面就是三个循环,外循环是列数,内层是i+1的状态j,最内是构成j的k状态。
C++ 代码
//状态压缩DP,与蒙德里安不同的是,这次的状态转移可以直接数出来,只有四种
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
const int MOD=1e9+7;
int f[N][4];//j为4种状态
int g[4][4]=//4种状态转移:当第i-1填满,i的状态决定i+1的状态
{
{1,1,1,1},
{0,0,1,1},
{0,1,0,1},
{1,0,0,0},
};
int main()
{
int n;
cin>>n;
f[0][0]=1;//初始为空,都是竖着放
for(int i=1;i<=n;i++)
{
for(int j=0;j<4;j++)
{
for(int k=0;k<4;k++)
{
if(g[k][j]==1)//判断组成j方案的k是否合法
{//即要判断由k状态是否能转移到j状态
f[i][j]=(f[i][j]+f[i-1][k])%MOD;
}
}
}
}
cout<<f[n][0];//n-1已经填满,符合要求
return 0;
}
6