链接

题意：有一个2 * N大小的画布，以及两种积木（i形和L形）,求出将画布排满共有多少种方式，积木可以旋转。

题解：用f[i][j]表示第i+1列为j的积木排序的最大次数。

f[1][0] = 1; //第1列满了 第i+1列为空的情况

f[1][1] = 1; //第1列满了 第i+1列上层被覆盖的情况

f[1][2] = 1; //第1列满了 第i+1列下层被覆盖的情况

f[1][3] = 1; //第1列满了 第i+1列全被覆盖的情况 为正方形时只统计横着放的 因为竖着放的后面会被统计到


//状态方程为：    
f[i][0]=(f[i−1][0]+f[i−1][3])//f[i-1][0]加一个竖着的i形 和 f[i-1][3]不加积木

f[i][1]=(f[i−1][0]+f[i−1][2])//f[i-1][0]加一个L形 和 f[i-1][2]加一个横着的i形

f[i][2]=(f[i−1][0]+f[i−1][1])//f[i-1][0]加一个L形 和 f[i-1][1]加一个横着的i形

f[i][3]=f[i−1][0]+f[i−1][1]+f[i−1][2]//f[i-1][0]加两个横着的i形 因为加竖着的i形的话与第一个重复 ） 和 f[i-1][1]加一个L形 和 f[i-1][2]加一个L形。

代码本题还可以用滚动数组优化

#include <iostream>
using namespace std;
const int N = 1e7 + 10;
const int mod = 1e9 + 7;
int f[N][5];
int main()
{
  int n;
  cin >> n;
  f[1][0] = 1; //第1列满了 第i+1列为空的情况
  f[1][1] = 1; //第1列满了 第i+1列上层被覆盖的情况
  f[1][2] = 1; //第1列满了 第i+1列下层被覆盖的情况
  f[1][3] = 1; //第1列满了 第i+1列全被覆盖的情况 为正方形时只统计横着放的 因为竖着放的后面会被统计到

  for (int i = 2; i <= n; i++)
  {
      f[i][0] = (f[i - 1][0] + f[i - 1][3]) % mod;
      f[i][1] = (f[i - 1][0] + f[i - 1][2]) % mod;
      f[i][2] = (f[i - 1][0] + f[i - 1][1]) % mod;
      f[i][3] = ((f[i - 1][0] + f[i - 1][1]) % mod + f[i - 1][2]) % mod;//因为是横着放 所以f[i-1][0]只有一种情况
  }
  cout << f[n][0] << endl;
}