状态压缩DP
定义：
状态压缩是一种使用二进制数来表示状态的方法，通常用于表示只有两种状态（0和1）的对象。
Acwing,291 蒙特里安的梦想
题目概览
求把 N × M N×M N×M的棋盘分割成若干个 1 × 2 1×2 1×2的长方形，有多少种方案。
例如当 N = 2 ， M = 4 N=2，M=4 N=2，M=4时，共有 55 55 55种方案。当 N = 2 ， M = 3 N=2，M=3 N=2，M=3时，共有 33 33 33种方案。
如下图所示：
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含两个整数 N N N和 M M M。
当输入用例 N = 0 ， M = 0 N=0，M=0 N=0，M=0时，表示输入终止，且该用例无需处理。
输出格式
每个测试用例输出一个结果，每个结果占一行。
数据范围
1 ≤ N , M ≤ 11 1≤N,M≤11 1≤N,M≤11
输入样例：
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例：
1
0
1
2
3
5
144
51205
思路：
假设我们当前的方格是这样的：
比如，我们先看一个简单情况，在一个 4 ∗ 3 4 * 3 4∗3的小方格中（蓝色），我们已经放好了横向的 2 ∗ 1 2 * 1 2∗1的小格子。
那么，剩下的格子纵向放只有一种情况，只能一列一列放。
所以， 2 ∗ 1 2 * 1 2∗1格子的摆放方案数等价于 2 ∗ 1 2 * 1 2∗1格子横向摆放的方法
f [ i ] [ j ] f[i][j] f[i][j]表示现在要摆第i列，j是一个二进制数，表示上一列有那些行伸出来了小方格到我这一列
FOR EXAMPLE:
比如，我现在在第三列，但是第二行由于上一列放置小方格导致已经被占用了，于是 j = ( 01000 ) 2 j=(01000)_2 j=(01000)2
即如图的情况
比如此时，矩阵是一个
5
∗
5
5 * 5
5∗5的情况，所以j是一个5位的二进制数,即
0
<
=
j
<
=
31
0 <= j <= 31
0<=j<=31
那么，我们如何转移呢？枚举一下 i − 1 i - 1 i−1列的所有状态
FOR EXAMPLE:
比如,我们当前要算的状态是这样的 f [ 3 ] [ 1 ] f[3][1] f[3][1]往前推，当前状态的表示图( j = ( 00001 ) 2 j = (00001)_2 j=(00001)2)为：
此时，我们枚举的上一个状态的j（称他为k）是 k = ( 10010 ) 2 k = (10010)_2 k=(10010)2,判断一下这个状态能否转移过来
能否转移过来的条件很简单:
-
j和k不能有冲突，如果冲突了，就会出现这样的情况：
那如何判断呢？利用位运算就可以啦~
当
(j & k) == 0时，即 j j j和 k k k是没有冲突的。 -
同一列上剩余的连续的空白格子一定是偶数个，不然竖着没法放
判断方式:
j | k不存在连续奇数个0时间复杂度: 4 ∗ 1 0 7 4 * 10^7 4∗107
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int N = 12,M = 1 << N;
int n ,m;//行数列数
long long f[N][M];//DP数组
bool st[M];//标记
int main(){
while(cin >> n >> m,n || m){//只要n,m不等于0就一直做
memset(f,0,sizeof f);//清一下f
//预处理是否出现连续奇数个0
for(int i = 0;i < 1 << n;i++){
st[i] = true;//假设它是成立的然后再来判断
int cnt = 0;//存储当前这段连续0的个数
for(int j = 0;j < n;j++)
if(i >> j & 1){//如果这一位是1
if(cnt & 1) st[i] = 0;//如果发现是奇数个，那么不成立
cnt = 0;//cnt清零
}
else cnt++;//否则是0，继续累加
if(cnt & 1) st[i] = 0;//最后cnt还需要判断一下
}
f[0][0] = 1;
for(int i = 1;i <= m;i++)
for(int j = 0;j < 1 << n;j++)
for(int k = 0;k < 1 << n;k++)
if((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
}