题目描述
求把NM的棋盘分割成若干个12的的长方形,有多少种方案。
例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。
输入格式
输入包含多组测试用例。
每组测试用例占一行,包含两个整数N和M。
当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个结果,每个结果占一行。
数据范围
1≤N,M≤11
分析
对于任意一种方案
要是 按照某一行为界限 横着切一刀
就有可能有这种情况 我们切到了 12的中间 或者 其他
1.如果我们切到了 12的中间 那么我们的 下一行 就必须 为这上一半 找到下一半
2.如果不是 这种情况 那么就随便放 但是 也得放得下
所以 我们把 行号 作为 DP的阶段 ,从第一行开始 不断向下拓展
//重点!!!!
我们用一个 M位二进制数字 其中第K位表示
如果第K位是 1 那么第K列 是一个 1*2的一半
K为0 就是 else
F[i,j] means 第i行的形态是 j 的情况下 前面i行 分割方案的总数
// 其中 j是用 十进制整数 记录的M位二进制数字
我们从 第 i-1 行 形态 k 转移到 第 i行的 形态 j的 时候
必须满足 如下条件
1. j&&K ==0
这保证了 每个数字 1 底下 都是 0 就是 另一半有着落了
2. j和k的按位或 运算 的结果的 二进制表示中 每一段连续的0 都是 偶数个
这些0 表示 可以横着放
代码实例
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
const int N=12;
long long f[N][1<<N];
bool st[1<<N];
int main()
{
while(cin>>n>>m,n||m)
{
// 1. 预处理一下 那些明显不符合条件的 列 就是有奇数个 空格的那种
for(int i=0;i<1<<n;++i)
{
int cnt=0;
st[i]=true;
// 上面是 枚举的过程
//现在是 每一个 都看一下
for(int j=0;j<n;++j)
{
if(i>>j&1) //就好像是 间断点一样
{
if(cnt&1) st[i]=false;
cnt=0;
}
else
cnt++;
}
if(cnt&1) st[i]=false;
// 这一步是为了 最后一位 不是 1 的情况下
// such as
// 10000 11110
}
memset(f, 0, sizeof f);//这一步 必不可少 因为有很多组啊 每一次的 f都是不一样的 朋友
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]) //这个 st[j|k] 什么意思呢? 就是 或了之后 产生的新的东西 有没有 符合 奇数个1的情况
f[i][j]+=f[i-1][k];
cout<<f[m][0]<<endl;
}
return 0;
}
参考文献
《算法竞赛进阶指南》