【题目来源】
AcWing：291. 蒙德里安的梦想 - AcWing题库
【题目描述】
求把 \(N\times M\) 的棋盘分割成若干个 \(1\times 2\) 的长方形，有多少种方案。
例如当 \(N=2,M=4\) 时，共有 \(5\) 种方案。当 \(N=2,M=3\) 时，共有 \(3\) 种方案。
如下图所示：
【输入】
输入包含多组测试用例。
每组测试用例占一行，包含两个整数 \(N\) 和 \(M\)。
当输入用例 \(N=0,M=0\) 时，表示输入终止，且该用例无需处理。
【输出】
每个测试用例输出一个结果，每个结果占一行。
【输入样例】
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
【解题思路】
【算法标签】
《AcWing 291 蒙德里安的梦想》 #动态规划# #状态压缩DP#
【代码详解】
!代码技巧#：判断连续0是否为偶数
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 15;
int n, m; //n行，m列数，编号从0开始，每一列状态有n位二进制数
//f[i][j]：前i-1列横放已好，第i列的伸出状态为j（不含在i列横放状态），各种来源集合
LL f[N][1<<N]; //f[N][2^N]
//st[j]:状态二进制数j 若0是连续偶数个则为true，合法，若存在连续奇数个0则为false，状态非法
bool st[1<<N]; //st[2^N]
int main()
{while (cin >> n >> m) {if (n==0 && m==0) break;memset(f, 0, sizeof(f)); //初始化方案数为0for (int i=0; i<1<<n; i++) { //预处理状态i，若存在连续奇数个数0则为falseint cnt = 0; //空单元格数量，即二进制i中含连续0数量st[i] = true;for (int j=0; j<n; j++) if (i>>j & 1) { // 二进制数i右移j为再与1做与运算。是1if (cnt%2==1) {st[i] = false; //统计连续0的数量，是奇数break;}cnt = 0; //统计下一个连续的0} else cnt++;if (cnt%2==1) st[i] = false; //最后一次还要特判一下}f[0][0] = 1; //边界：因为第0列不会有-1列的突出出俩，0列状态全是0，有1个方案for (int i=1; i<=m; i++) //枚举所有列for (int j=0; j< 1<<n; j++) //枚举i列状态j，选出由i-1列横放产生的状态jfor (int k=0; k< 1<<n; k++) //枚举i-1的状态if ((j&k)==0 && st[j|k]) //条件前i-1列横放有效f[i][j] += f[i-1][k];//结果：前m-1列（所有列）横放有效，没有向m列伸出（状态为0）cout << f[m][0] << endl;}return 0;
}
【运行结果】
1 2
1
1 3
0
1 4
1
2 2
2
2 3
3
2 4
5
2 11
144
4 11
51205
0 0