题目描述

本题是蒙德里安的梦想的一个缩减版（状态压缩dp） 因为它的行数只有2行 n列
首先我们dp数组 表示的是已经完成了i-1行且第i行的状态为j i-1行已经全部塞满
我们要知道第i-1行的状态能否转移到第i行并且转移后是什么状态

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e7 + 10, mod = 1000000007;
int f[N][4];  //f[i][j]表示已经处理好前i - 1行并且第i行的状态为j的方案的集合
int g[4][4] =   //g数组的一维表示第i-1行的状态也就是初始状态
{               //二位表示第i行的状态也就是目标状态
  {1,1,1,1},    //举个例子 比如说g[1][1]的意思就是初始状态为01 目标状态为01
  {0,0,1,1},    //g[1][1]等于0 也就代表这初始状态01无法转移到目标状态01
  {0,1,0,1},
  {1,0,0,0}
};

int main()
{
  int n;
  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];   
}