状态压缩DP

当把所有横向格子放完后，纵向方格的排放方案只有一种。因此整个划分方案数与横着摆放方格的方案数相同。

f[i, j]表示，目前摆放第i列，j是二进制数（状态是整数，看成二进制数，位上的0或1代表不同的情况，这是状态压缩的核心），如果有n行，则j=1~2n-1，表示存储本行在第i-1列伸出横向1x2小方格的情况。

更新的条件（k是上一个状态的j）：

1. 可以从第i-2列伸到第i-1列的行与从第i-1列伸到第i列的行不能重复。即 j&k == 0

2. 第i-1列所有剩余的连续的空白格子一定要是偶数。即j | k 不存在连续奇数个0. (可以先预处理)

转移的公式：f[i, j] = f[i - 1, k].

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N = 12, M = 1 << N;  //N是i的状态，M是j的状态
 7 int n, m; //矩形的行数和列数
 8 long long f[N][M];
 9 bool st[M]; //存储能存在连续奇数个0的状态 
10 
11 int main(){
12     int n, m;
13     while(cin >> n >> m, n || m){
14         memset(f, 0, sizeof f);
15         //预处理是否所有状态不能存在连续奇数个0
16         for(int i = 0; i < 1 << n;i ++ ){
17             st[i] = true;
18             int cnt = 0;//当前连续0的个数
19             for(int j = 0; j < n; j ++ )
20             {
21                 if(i >> j & 1)//当前这一位是1，上一段0已经截止了
22                 {
23                     if(cnt & 1) st[i] = false;//连续的0是否有奇数个，有奇数个则第i个状态不合法
24                     cnt = 0;
25                 }
26                 else cnt ++ ;
27             }
28             if(cnt & 1) st[i] = false; // 判断最后一段0的个数，要是奇数
29         }
30 
31         f[0][0] = 1; 
32         
33         for(int i = 1;i <= m; i ++ )
34             for(int j = 0; j < 1 << n; j ++ )
35                 for(int k = 0; k < 1 << n; k ++ )//枚举第i-1列的所有状态
36                     if((j & k) == 0 && st[j | k])
37                         f[i][j] += f[i - 1][k];
38         
39         cout << f[m][0] << endl;//最后一列是m-1列，当m列没有捅出来任何方块的时候才是合理方案
40     }
41     return 0;
42 }