题目描述
求把NM的棋盘分割成若干个12的的长方形,有多少种方案。
例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。
如下图所示:
输入格式
输入包含多组测试用例。
每组测试用例占一行,包含两个整数N和M。
当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个结果,每个结果占一行。
数据范围
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
思路
核心:
摆放的小方格方案数 等价于 横着摆放的小方格方案数
如何判断当前方案是否合法?
遍历每一列,i列的方案数只和i-1列有关系
1.j&k==0,i-2列伸到i-1的小方格 和 i-1列伸到i的小方格 不重复。
2.每一列,所有连续着空着的小方格必须是偶数个
dp定义:
状态表示 f[i][j]: 前i-1列已经确定,且从第i-1列伸出的小方格在第i列的状态为j 的方案数。属性:数量。
i=2, j=11001 表示下列图的状态
但是i-1, i列已经固定,所以集合划分是依据i-2 列伸到 i-1 列的不同状态 k 来划分
i-2 列伸到 i-1 列的状态 k=00100
状态计算:(限制条件:i-1列非空白位置可以不能放置小方格),在i列不同的放置方法就是不同的集合划分。
问题:第 i-2 列伸到 i-1 列的状态为 k , 是否能成功转移到 第 i-1 列伸到 i 列的状态为 j ?
需要满足如下条件:
j&k==0, i-2列伸到i-1的小方格 和 i-1列伸到i的小方格 不重复。
每一列,所有连续着空着的小方格必须是偶数个
f[m][0]:
列数从0开始计数,m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
c++
#include <iostream>
#include <cstring>
using namespace std;
//数据范围1~11
const int N = 12;
//每一列的每一个空格有两种选择,放和不放,所以是2^n
const int M = 1 << N; //2^n次方个状态 12个位, 每位0或者1
//方案数比较大,所以要使用long long 类型
//f[i][j]表示 i-1列的方案数已经确定,从i-1列伸出,并且第i列的状态是j的所有方案数
long long f[N][M];
//第 i-2 列伸到 i-1 列的状态为 k , 是否能成功转移到 第 i-1 列伸到 i 列的状态为 j
//st[j|k]=true 表示能成功转移
bool st[M];
//n行m列
int n, m;
int main(){
//预处理st数组
//不同状态(n位 0或者1 组成的状态,st存储的不同状态下,连续0位置是否为偶数)
//比如 10010 连续的0中有一处为奇数个数,明显没法放列长度为1 * 2的长方形方块
while(cin >> n >> m, n || m){
for(int i = 0; i < 1 << n; i ++){//枚举所有状态
// 第 i-2 列伸到 i-1 列的状态为 k ,
// 能成功转移到
// 第 i-1 列伸到 i 列的状态为 j
st[i] = true;
//记录第j列中连续0是否存在奇数个数
int cnt = 0;
for(int j = 0; j < n; j ++){//因为是n位0或者1,通过右移来获得每一位的数字
// 通过位操作,i状态下j行是否放置方格,
// 0就是不放, 1就是放
if(i >> j & 1){ //如果是1
// 如果放置小方块使得连续的空白格子数成为奇数,
// 这样的状态就是不行的,
if(cnt & 1){
st[i] = false; //将状态i置为false
break;
}
}else{
cnt ++; // 0的个数
}
}
//处理剩余的格子情况
if(cnt & 1) st[i] = false;
}
// 初始化状态数组f
memset(f, 0, sizeof f);
// 棋盘是从第0列开始,没有-1列,所以第0列第0行,不会有延伸出来的小方块
// 没有横着摆放的小方块,所有小方块都是竖着摆放的,这种状态记录为一种方案
f[0][0] = 1;
// 遍历每一列
for (int i = 1; i <= m; i++) {
// 枚举i列每一种状态
for (int j = 0; j < 1 << n; j++) {
// 枚举i-1列每一种状态
for (int k = 0; k < 1 << n; k++) {
// f[i-1][k] 成功转到 f[i][j]
if ((j & k) == 0 && st[j | k]) {
f[i][j] += f[i - 1][k]; //那么这种状态下它的方案数等于之前每种k状态数目的和
}
}
}
}
// 棋盘一共有0~m-1列
// f[i][j]表示 前i-1列的方案数已经确定,从i-1列伸出,并且第i列的状态是j的所有方案数
// f[m][0]表示 前m-1列的方案数已经确定,从m-1列伸出,并且第m列的状态是0的所有方案数
// 也就是m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
cout << f[m][0] << endl;
}
return 0;
}