题目描述
蒙德里安的梦想:这题比较困难,请做好准备
求把 N×M的棋盘分割成若干个 1×2的长方形,有多少种方案。
例如当 N = 2,M = 4时,共有 5种方案。当 N = 2,M = 3
时,共有 3种方案。
如下图所示:
输入格式:
输入包含多组测试用例。
每组测试用例占一行,包含两个整数 N和 M
当输入用例 N = 0,M = 0
时,表示输入终止,且该用例无需处理。
输出格式:
每个测试用例输出一个结果,每个结果占一行。
----------
### 算法:状态压缩DP
比起切割棋盘,不如我们自己放棋到棋盘上,可以横着放,也可以竖着放
当我们先把横着放完棋时,竖着放的棋别无选择,只能一列一列放
也就是说实际上我们要求的放置数和我们横着放棋的方案数是相等的,因为横着放完了之后,竖着的棋位置已经确定,只能顺次放置,不能再改变
这个过程可以画图思考,横着的放完,竖着的棋就没有可变化的空间了,因此划分的方案数等同于横着放棋的方案数
那么现在来看我们需要横着放棋,那么题目要求必须使整个棋盘被完全划分,也就是说不能出现有空格但竖着的横着的棋没有放上去
因为我们是先横着放棋的,那么就需要从横着放的时候注意,以后再放竖棋的时候,必须让竖棋填满整个还空着的区域
举个例子来看: *表示被放了棋的位置,-表示还没有放棋的空位置,*和-都表示一个长度为1的小方格,先来看2*3的棋盘,先来看横着放棋
- - - ----------> * * - -----> * * *
- - - * * - * * *
1.
//可见方案1的放棋方式是可以的,我们将棋竖着放到最后一列的时候,整个棋盘被恰好划分为两个横着的,一个竖着的,该方案是合法的
那么怎么放就是不合法的?现在来看一下不合法的放置方案,还是先放横着的
- - - ----------> - * *
- - - * * - --------->没法放竖着的棋
2.
那么这个放置方案就不行,按列看看空着的格子,我们发现合法的方案1,空着的格子(最后一列)它是连续的两个空着的格子,也就是说列上有连续的偶数个空着的格子
而这个不合法的方案2,空着的格子(第一列是1个空着的格子,最后一列也是1个空着的格子)奇数个空着的格子,那么它就是不合法的
方案的合法性是否有关列上(连续)空着的格子的奇偶数?扩展到3*3看看:
- - - * * - * * - * * -
- - - --------> - * * * * - * * - ---------->都没法放竖着的棋
- - - * * - * * - - * *
// 1. 2. 3.
///这三种放置方式都是不合法的,也都出现了连续的奇数个空位置,确实不合法,不过实际上 奇数*奇数的棋盘划分方式无论怎么放都不合法,这里只是演示以下错误的方案
通过上面的讨论,我么发现,一种方案是否合法和其每一列的所有连续的空着的格子数有关系
每一列内部所有连续空着的格子的数量需要时偶数个时,那么此方案才合法,在放置横着的格子时,需要格外注意
那么这个题是一个dp问题,我们还是要从集合角度去思考,我们需要将每一行上棋的放置状态表示出来,这就需要用到状态压缩的思想
我们怎么样表示每一行的棋的状态?这个确实很难想,下面给出结论:
f[i,j]表示前i-1列已经摆好所有棋,且有横着放的棋从第i-1列,伸出到了第i列上 的所有方案中的状态是j,j是一个二进制的数
///这句话已经不像是人说出来的了,更像是卡密
我们还是举个例子来看:5*5,注意这个划分方式不可能有解,下面只是举个例子来看这个集合的实际含义
- - - - -
- - - - -
- - - - -
- - - - -
- - - - -
//假设我们取i为2,也就是第3列:i-1就是第2列
i-1 i i-1 i
- - - - - - * * - - 1
- - - - - - * * - - 1
- - - - - - - - - - 0 j=11001
- - - - - - - - - - 0
- - - - - - * * - - 1
1.
//啥叫从第i-1列伸出到第i列?因为棋是横着放的,横着的长度是2,小格子长度是1,那么横着的棋肯定会占两列
从i-1列伸到i列就是再说棋的左边占第i-1列,右边占第i列,这个棋就占了两列
//举个例子就是:上图1的1 2 5行都有棋从第i-1列伸到第i列,并且前i-1列已经摆好了横着的棋,不用管前i-1列了,我们现在将这个棋盘的状态叫做状态j
那么具体的j到底是啥?我们现在将满足前i-1列已经摆满棋这个大前提下,同时满足有棋从第i-1列伸到第i列的行叫做1,没有伸出来的行叫做0
//那么1.中125行伸出来了,那就是1,34没有伸出来就是0,竖着读出来每一行的编号:11001,这串01组成的二进制数就叫做数字j
j就可以表示整个棋盘的状态,用图更形象地表示就是附图,1表示此行有伸出的棋,0表示此行没有伸出的棋
集合弄清楚了以后,我们再来思考状态划分,大多数情况下,分割集合按照最后一步操作来划分,每个状态依赖于前一个状态
我们按照i-2伸出到i-1列的棋盘状态来划分集合状态,假设每个从i-2伸到i-1列的状态是k,k和j一样就是一个二进制数,还是拿上面那个举例:
i-2i-1 i
- * * - -
- * * - -
* * - - -
- - - - -
- * * - -
假设有一个状态k,他表示的是第三行有棋从第i-2列伸出到了第i-1列的状态,那么k就是00100,接着就可以从这个倒数第二步推到我们要求的f[i,j]了
这个倒数第二步就是集合f[i-1,k],带入一下集合实际含义,f[i-1,k]就是前i-2列已经摆好,并且有棋从第i-2列伸出到第i-1列的棋盘的状态是k
这个就是我们所求的f[i,j]所依赖的前一种状态(或者说倒数第二步),我们只需要求出所有f[i-1,k]的集合的所有方案数之和就是f[i,j]的划分方案数
对于f[i-1,k]来说为了使整个棋盘的划分合理,需要对其限制,在放完倒数第二步f[i-1,k]时对最后一步f[i,j]的放置是有影响的,需要对其进行限制
我们放i-2到i-1的棋的时候,不能在同一行放置i-1到i的棋,否则就会重叠,举个例子:
i-2i-1 i
- - - - -
- - - - -
* * * - - k是00100,j是00100,这是不合法的
- - - - -
- - - - -
第三行的倒数第二步在第三行横着放了棋,那么此时k就是00100,此时就不能在第三行横着再放从i-1到i的棋,这样两个棋就会在i-1列重叠,这不合法
//那么我们转化成代码含义,k第三行放棋就是k为00100,假设j也在第三行放棋,j也就是00100,由于j和k不能在同一行放棋,这时不合法的,此时的j&k就是00100,而这是不合法的,1就是表示在这一行横着放棋
也就是说 k&j不能是1(如果是1说明k和j的同一位上有1,也就是同一行上放了两个重叠的棋,这是不合法的),那么就必须满足j^k==0
同时还得满足所有连续空着的位置数必须是偶数,这样才能在竖着放棋得时候保证填充满整个棋盘.这个转化成代码含义待会再说
我们先来看看最终结果是啥,他说恰好将整个棋盘划分完全,也就是前m-1列(从0开始编号)全部摆好了
那么就是f[m,0],实际含义是前m-1列已经摆好,并且从m-1列(最后一列)伸到m列(超出期盼边界得一列)的所有状态j是0
j是0的话也就是0000000000.......,表示没有任何一行有棋从m-1列伸到m列,这就是我们所要求的,答案就是f[m,0]
本题的最多11个格子,也就是j长00000000000 11,对于每一个位置都可能有1或者没1,那么j最多就是有2^11个
这个其实好说,比如开头两个位置举例:
1.最开始可以伸出也可以不伸出 就是10000000000或者是0000000000 ,两种状态,2^1
2.第二个也是,多出来 1100000000或者是01000000000,那就是4中方案,2^2,一共有11个位置最多也就是2^11种方案
也就是说j最大是2^11,所有状态就是从000000000--->111111111的状态数量,这个二进制数的范围也就是0----2^11
//小技巧:1<<n就等于2的n次方,1<<n也就是j的上界(n表示棋盘的行数,也就是二进制数j的长度),那么二进制数j的最大就是1<<n
//这个题的代码也非常难懂,我会分块来说:
#### C++ 代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 12;//表示j的长度是多少,多开一个
const int M = 1 << N;///表示长度为N的二进制数的个数,也就是j的上界
int n, m;
LL f[N][M];///第二维是二进制数j,上界就是1<<N
vector<int> state[M];///表示当前状态j是由哪个状态k转移而来的
bool st[M];///判断这种状态是否合法
int main()
{
while (cin >> n >> m, n || m)
{
///我们首先来处理第二种情况导致的不合法的方案
///第二种情况是连续的空格子个数必须有偶数个
///这个用代码怎么表示?还是通过二进制数j来控制,我们首先明白,连续的空格子是用来放竖着的棋的,不关横着的棋的事
///比如说有5*5的划分:
/// i-1 i
/// - * * - - 1
/// - * * - - 1
/// - - · - - 0 j是11001
/// - - · - - 0
/// - * * - - 1
///现在来看0表示这一行上没有棋从i-1列伸到i列上去,那么也就是说这一行中第i列是空着的,用·表示
///·的数量就是空格子的数量,·的数量连续且必须是偶数,这也就代表着j中连续的0的数量必须是偶数,不能是奇数,否则不合法
///换到j身上就是j中连续的0的数量必须是偶数,否则状态j不合法,被pass掉,我们将在下面的代码中首先预处理出来从0--->111111..的方案中哪些状态j是不合法的
for (int i = 0; i < 1 << n; i++)///枚举所有的二进制数j,看看哪些j是合法的
{
int cnt = 0;///统计j中连续的0是否是奇数
bool is_valid = true;//判断i状态是否合法
for (int j = 0; j < n; j++)///二进制数长度是n,i这个二进制数每次向右移动j位就是再查看i每一位是1还是0
{
if (i >> j & 1)//遇到1就停止,并查看这一段的0的数量是否是奇数
{
if (cnt & 1)//是奇数,不合法
{
is_valid = false;
break;
}
cnt = 0;//置为0接着看下一段0的个数,判断下一段是否合法
}
else cnt++;///遇到0统计个数
}
///处理i二进制数中最后一段0的个数,为奇数也一样不合法
if (cnt & 1) is_valid = false;
st[i] = is_valid;///判断状态i是否合法
}
///预处理结束后,再结合条件1:k&j==0来看哪几种方案是合法的,累加起来就是最终解
for (int i = 0; i < 1 << n; i++)///由j更新i
{
state[i].clear();
for (int j = 0; j < 1 << n; j++)
if ((i & j) == 0 && st[i | j])///如果两个条件都满足,那就合法
state[i].push_back(j);///i由j更新而来,或者说i由j转移而来
///需要解释,st[i|j]是什么意思,st[i]=true表示状态i是合法的
///i|j的意思是由j更新i,也就是说i状态由j状态转移而来的,我们需要判断这种转移是否是合法的,合法才能说明i状态依赖于j状态,i是由j状态转移而来
//我们将这项转移也成为一次操作
///也就是说如果有:
/// k
/// - - * * - 1
/// - - * * - 1
/// - - - - - 0 j一开始是11001,表示第34行的第k列是空着的,我们枚举下一个状态i假设是:
/// - - - - - 0
/// - - * * - 1
/// k
/// - - * * - 1
/// - - * * - 1
/// - - * * - 1 i又填充了一行,i就是11101,i|j就是11101(成功保留了这项操作的结果),因此i|j就是当前操作所导致的最终状态(是1了就是被填充了,是0说明以前没被填充,现在还没被填充)
/// - - - - - 0
/// - - * * - 1
///我们的操作必须是合法的,也就是操作完的最终状态i|j必须是合法的,因此用st[i|j]判断我们操作完的状态是否是合法的,合法的才能执行此操作
///才能说用j来更新状态i是合法的
}
///预处理完所有合法方案,累加上一步的f[i-1,k]就是当前的f[i,j]
///f[m,0]即为所求
memset(f, 0, sizeof f);
f[0][0] = 1;//空棋盘就是最初的一种方案
for (int i = 1; i <= m; i++)/////i就是列数
for (int j = 0; j < 1 << n; j++)///每一种状态
for (auto k : state[j])///枚举其上一个状态
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}