问题描述
求把 N×M 的棋盘分割成若干个 1×2 的的长方形,有多少种方案。
思路详解(推荐看看,也可以直接看代码)
相当于,用 1x2 的长方形填 NxM 的棋盘,有多少种合法方案。合法指填满。
又相当于,用横着的 1x2 的长方形填棋盘,有多少种合法方案。合法指用竖着的长方形能填满剩余的。
所以我们只考虑摆放横格子的合法方案就ok了
总体打算按列从小到大地排列横格子。
那么先考虑每一列要怎么摆放横格子,涉及摆放的位置和个数
可以发现,这列格子摆放的位置和个数,相当于这列摆放的状态。
每列中,摆放的状态会受行数n的限制,行数多1,就能多摆放1个,状态个数翻倍x2
所以全部状态的个数为 2^n (1 << n) (c/c++ ^不是求幂,而是亦或运算)
重点来了,列与列之间的状态并不是孤立的。
我们从小到大摆放列,意味着,前一列的状态会影响当前列的状态。
当前一列某行的有格子伸到当前列时,当前列的这一行就不能有再有格子伸到下一列
简单来说,就是某列的某行有尾格子后,在这行就不能有头格子。头格子尾格子的下方有定义
通过这样的过程,我们就能得到摆放所有横格子的方案数。
但是我们还需要在过程中,筛掉不能用竖格子填满剩余的空格的方案数
怎么筛?
能用的竖格子填满也就意味着存在连续的为偶数个数的空格子(状态为0)
所以筛掉连续的为奇数个数的0的方案数就可以了。
状态转移过程总结-两个要点
1.某列某行不同时存在头尾格子。(前后两列格子不冲突)
2.筛掉连续奇数个0的状态
代码中的预处理就是处理这两个。
一些重要但有些绕的概念(可以跳过也可以结合来理解)
状态表示 f[i][j]
: 前i-1列已经确定,且从第i-1列伸出的小方格在第i列的状态为j 的方案数。
j | k
第i - 1 行的1的个数,就是当前 第i-1列的到底有几个1,既有第i - 2行捅过来的尾部,也有从第i - 1行捅到第i的头部
j & k
第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行)
名词定义
为了表达方便,个人定义,i-2列捅(伸)到i-1列的格子,在i-2列称为头格子,在i-1列称为尾格子
又如,第i-1列伸到第i列的格子,对于第i列来说,这叫尾格子,但对第i-1列来说,这是头格子。
更新后的概念
有了名词定义,上面的概念可以简化了
f[i][j]
:前i-1列已经确定,第i列的尾格子状态是j的方案数
j | k
计算第i - 1列所有格子(1)的个数。也就是第i - 1列真实的状态。(尾格子 | 头格子 得到 所有格子(1))
j & k
第i - 1行头格子和尾格子没有冲突的状态
代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
LL f[N][M];// 第一维表示第几列,第二维表示该列尾格子的状态(被捅的状态)
bool st[M];//一列最多有11行,每行两种状态,所以一列有2^11(1<<11)种状态,这里true表示这个状态没有连续奇数个0.
vector<int> state[M];//state[j]存储的是第i列合法的i - 1列的状态
//合法的含义:1.i-1列的头格子和尾格子没有冲突,i-1列没有连续奇数个零。
int m, n;
int main()
{
while (cin >> n >> m, n || m) //读入n,m,当n和m没有同时为0就继续读入
{
//预处理st数组,哪些状态是没有连续奇数个零的?true表示没有连续奇数个零的状态
for (int i= 0; i < 1 << n; i ++ )//循环每种状态,用一个数来表示一列的行选择状态,化零为整
{
int cnt = 0;//连续0的个数
bool isValid = true;//默认这种状态是true的,是没有连续奇数个零的
for (int j = 0; j < n; j ++ )//遍历这种状态的每行的选择,化整为零
{
if(i >> j & 1)//这行的状态是1
{
if (cnt & 1)//若前面连续的0的个数是奇数
{
isValid = false;
break;
}
//前面连续的0的个数是偶数,现在遇到了一个1
cnt = 0; //之所以清理,因为我们定义了cnt是连续0的个数。当然cnt不清零也行,那cnt就定义为0的个数就不矛盾了
}
else cnt ++ ;
}
if (cnt & 1) isValid = false; // 有可能最后的状态都是0,无法进入if判断,需要在这里特判一个。
st[i] = isValid; // 这样i状态是否合法就得到了。循环1 << n 次,将判断所有的状态是否合法且存储下来。
}// 时间花费 2^11 * 11 = 22528 加上常数的话,大于O(10^5) << O(10^7)这个预处理时间毛毛雨
//预处理state数组,哪些状态k可以放在某个状态j的前面的?可以就state[j].push_back(k);
for (int j = 0; j < 1 << n; j ++ ) //循环第i列的所有状态
{
state[j].clear(); //清空上次操作遗留的状态,防止影响本次状态。毕竟不只是进行一次。
for (int k = 0; k < 1 << n; k ++ ) // 循环第i - 1列的所有状态
if ((j & k) == 0 && st[j | k])
state[j].push_back(k);
}
//开始dp
memset(f, 0, sizeof f);////清空上次操作遗留的状态,防止影响本次状态。毕竟不只是进行一次。
f[0][0] = 1; //初始化,第0列之前已经确定,第0列尾格子=0的方案数为1(第-1列什么格子都没有,所以第0列没有尾格子)
//其他如,f[0][1..n] 要求第0列有1..n 个尾格子的方案数都为0,第零行只有头格子。
for (int i = 1; i <= m; i ++ ) //遍历每一列:第i列合法范围是(0~m-1列)
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; //f[m][0] 表示前m - 1行已经确定,第m行有0个尾格子的方案数。也就是第m-1行没有头格子的方案数。
}
return 0;
}
参考
https://www.acwing.com/solution/content/5121/
https://www.acwing.com/solution/content/28088/
写得好呀,感谢