状压dp好抽象,这题要是没理解的话,是真的难>︿<,但是这题又是一道非常非常非常经典的状压dp入门题。

题目描述

求把 $N * M$ 的棋盘分割成若干个 $1 * 2$ 的的长方形,有多少种方案。

例如当 $N = 2$,$M = 4$ 时,共有 $5$ 种方案。当 $N = 2$,$M = 3$ 时,共有 $3$ 种方案。

如下图所示:

image.png

输入格式

输入包含多组测试用例。

每组测试用例占一行,包含两个整数 $N$ 和 $M$。

当输入用例 $N = 0$,$M = 0$ 时,表示输入终止,且该用例无需处理。

输出格式

每个测试用例输出一个结果,每个结果占一行。

数据范围

$1 \le N , M \le 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

思路

这里小长方形就用小方块代替了

题目分析

题目说的是将棋盘分割成若干个 $1 * 2$ 的小方块,问方案数。这里分割不好想,不妨我们换个角度来想,我们可以将题目转化为将若干个 $1 * 2$ 的小方块放入棋盘中,问有多少种放法

通过分析可以发现:只要确定了横着的小方块的放法,那么竖着的小方块的放法就被唯一确定了

那么最后要求的将若干个小方块放入棋盘中的合法方案数就等于横着放小方块的合法方案数

所以这里可以把问题简化为求横着放小方块的合法方案数

那么又有了个新的问题,如何判断当前方案是合法的呢?

根据我们之前的分析,所有剩余的位置,只要能填充满竖着的小方块,那么这个方案就是合法的。因为我们是先放横着的小方块,所以可以按列来看,每一列内部所有连续的空着的小方块,必须是偶数个。

为什么必须是偶数个呢?因为如果是奇数个的话,那一定会有一个位置是空着的,小方块放不进去。

思路

  • 状态表示: $f[i, j]$ 表示已经将前 $i - 1$ 列摆放好,且从第 $i - 1$ 列伸出到第 $i$ 列的状态为 $j$ 的所有方案。
    这里状态 $j$ 是一个二进制数,第 $k$ 位为 $0/1$ 表示第 $i - 1$ 列 没有/有 伸出来,例如下面这种放法,$j$ 就可以表示为 $110001$
    image.png

  • 状态计算:既然第 $i$ 列已经固定了,那么我们要考虑的就是第 $i - 2$ 列是怎么 转移到第 $i - 1$ 列的。假设此时 第 $i - 1$ 列的状态为 $k$ ,$k = 00100$,对应的方案数为 $f[i - 1, k]$,即前 $i - 2$ 列都已摆完,且从第 $i - 2$ 列伸到第 $i - 1$ 列的状态为 $k$ 的所有方案数。
    不是所有的状态 $k$ 都是合法的,那么这个 $k$ 应该满足什么条件才可以呢?

    1. 首先 $k$ 和 $j$ 必须不冲突,也就是 $k$ 和 $j$ 不能在同一行,也就是小方块之间不能有覆盖,如下图
      image.png
      这个在同一行就冲突了,所以需要满足 $(k \ & \ j) == 0$ ,与($&$)运算,两位同时为“1”,结果才为“1”,否则为0。在这里就表示 $k$ 和 $j$ 没有一位对应位都是1的情况,即代表 $k$ 和 $j$ 没有冲突。
    2. 该列所有连续的空着的位置长度必须是偶数
  • 初始化:$f[0,0] = 1$,初始时第 $0$ 列左边是空的,所以不会有任何一个小方块伸出来,所以 $f[0,0]$ 所表示的是一个合法状态,所以初值是 $1$。

解释以下代码中的 $st[j \ | \ k]$,我们已经知道 $st$ 数组表示的是这一列没有连续奇数个 $0$ 的情况,这个 $j \ | \ k$ 就是当前第 $i - 1$ 列的有几个 $1$,即哪几行是横着放方块的。

参考代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];	// 第一维表示列, 第二维表示所有可能的状态
vector<int> state[M];	// 记录当前状态可以从哪些状态转移过来
bool st[M];	// 存储每种状态是否有奇数个连续的0,如果奇数个0是无效状态,如果是偶数个0置为true。

int main()
{
    while (cin >> n >> m, n || m)
    {
        // 预处理,对于每种状态,每列不能有奇数个连续的0
        for (int i = 0; i < (1 << n); i ++ )
        {
            int cnt = 0;
            bool is_valid = true;
            for (int j = 0; j < n; j ++ )
            {
                if ((i >> j) & 1)
                {
                    if (cnt & 1)
                    {
                        is_valid = false;
                        break;
                    }
                }
                else cnt ++ ;
            }
            if (cnt & 1) is_valid = false;
            st[i] = is_valid;
        }
        
	// 预处理当前状态可以从哪些状态转移过来
        for (int j = 0; j < (1 << n); j ++ )
        {
            state[j].clear();
            for (int k = 0; k < (1 << n); k ++ )
                if ((j & k) == 0 && st[j | k])
                    state[j].push_back(k);
        }
        
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        
        for (int i = 1; i <= m; 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;
}

Q.E.D.