题目描述

Bugs Integrated, Inc 是高级存储芯片的主要制造商。

他们正在生产一种新的 6TB Q-RAM 芯片。

每个芯片由六个单位方块组成，以 $2 \times 3$ 矩形的形式排列。

该公司通过分割 $N \times M$ 个单位方块组成的矩形硅片得到多个 Q-RAM 芯片。

大的矩形硅片会被完整检测，并且其中坏掉的方块会用黑色标明。

矩形硅片要被分割成尽可能多的芯片，并且每个芯片中都不能包含坏掉的方块，请你求出最优解法。

输入格式

第一行包含整数 $D$，表示共有 $D$ 组测试数据。

每组测试数据第一行包含三个整数 $N,M$ 和 $K$，其中 $K$ 为坏掉的方块数量。

接下来 $K$ 行，每行包含两个整数 $x,y$，表示一个坏掉的方块的位置坐标 $(x,y)$。（矩形硅片的左上角坐标为 $(1,1)$，右下角坐标为 $(N,M)$）

输出格式

每组测试用例输出一个整数，表示能分割出的最大芯片数量。

每个结果占一行。

样例

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

3
4

样例解释

第一组数据

$N=6, M=6, K=5$ 坏块位置： (1,4), (4,6), (2,2), (3,6), (6,4)

需要将 $6\times 6$ 的硅片分割成尽可能多的 $2\times 3$ 或 $3\times 2$ 的芯片（芯片可以旋转吗？题目说“以 $2\times 3$ 矩形的形式排列”，没有明确说明是否可以旋转为 $3\times 2$，但通常可以旋转，因为芯片是矩形，摆放方向可以旋转）。

分割方案

可以分割出 3 个芯片，例如：

• 一个 $2\times 3$ 芯片覆盖 (1,1)-(2,3)
• 一个 $2\times 3$ 芯片覆盖 (1,4)-(2,6) 但 (1,4) 是坏块，不行。 所以可能旋转放置。

实际需要尝试所有可能放置方式。

输出 3。

第二组数据

$N=6, M=5, K=4$ 坏块： (3,3), (6,1), (6,2), (6,4)

最大芯片数为 4。

数据范围

• $1 \le D \le 5$
• $1 \le N \le 150$
• $1 \le M \le 10$
• $1 \le K \le N \times M$

算法分析

这是一个棋盘覆盖问题，要求用 $2\times 3$ 或 $3\times 2$ 的矩形（芯片）覆盖 $N\times M$ 的网格，不能覆盖坏块，求最多能放的芯片数量。

由于 $M \le 10$，很小，可以使用状态压缩动态规划。

状态定义

因为芯片是 $2\times 3$ 或 $3\times 2$，会影响连续三行的状态，所以需要用三行的状态来表示。

设 $dp[i][mask1][mask2]$ 表示处理到第 $i$ 行，当前行状态为 $mask1$，上一行状态为 $mask2$ 时，前 $i$ 行能放置的最大芯片数。其中状态 mask 的二进制位表示该格子是否被覆盖（1 表示被覆盖，0 表示未覆盖）。

但这样状态数太大：$150 \times 2^{10} \times 2^{10} = 150 \times 1024 \times 1024 \approx 1.57\times 10^8$，可能过大。

另一种常见方法：轮廓线动态规划（插头 DP 或骨牌覆盖 DP）。

由于芯片尺寸是 $2\times 3$ 或 $3\times 2$，我们需要考虑连续三行的放置。可以用滚动数组，状态为当前行和上一行的覆盖情况。

预处理

将坏块信息存入数组 $bad[i][j]$ 表示 $(i,j)$ 是否为坏块。

状态表示

设 $f[i][S]$ 表示处理到第 $i$ 行，且第 $i$ 行的覆盖状态为 $S$（$S$ 是一个 $M$ 位二进制数，1 表示该格子被之前的芯片覆盖，0 表示未被覆盖）时的最大芯片数。

但这样不够，因为 $3\times 2$ 的芯片会跨越三行，需要知道前两行的覆盖情况。所以状态需要包含当前行和上一行的覆盖状态。

更精确地，设 $dp[i][j][mask]$ 表示处理到第 $i$ 行第 $j$ 列，当前行和上一行的覆盖状态为 $mask$（$mask$ 是一个 $2M$ 位的二进制数，前 $M$ 位表示上一行，后 $M$ 位表示当前行）时的最大芯片数。但这样状态数 $150 \times 10 \times 2^{20} \approx 150 \times 10 \times 1e6 = 1.5e9$，太大。

优化

由于 $M \le 10$，我们可以用三进制状态表示每个格子的情况：0 表示未覆盖，1 表示被覆盖且是 $2\times 3$ 芯片的一部分，2 表示被覆盖且是 $3\times 2$ 芯片的一部分？但这样复杂。

实际上，由于芯片尺寸固定，我们可以枚举每行放置芯片的方式，然后进行 DP。

一种经典解法：使用 DFS 枚举当前行放置芯片的所有可能方式，然后进行状态转移。

定义 $f[i][S]$ 表示前 $i-1$ 行已经填满（即没有未覆盖的可用格子），且第 $i$ 行的状态为 $S$（$S$ 的二进制表示第 $i$ 行哪些格子被覆盖）时的最大芯片数。

转移时，我们枚举第 $i$ 行和第 $i+1$ 行如何放置芯片（因为 $2\times 3$ 芯片可能占据两行，$3\times 2$ 芯片可能占据三行）。但这样需要同时考虑三行。

更具体地，我们可以用 $f[i][S1][S2]$ 表示前 $i-1$ 行已经填满，第 $i$ 行覆盖状态为 $S1$，第 $i+1$ 行覆盖状态为 $S2$ 时的最大芯片数。其中 $S1$ 和 $S2$ 都是 $M$ 位二进制数，1 表示该格子被覆盖（可能是上一行放置的芯片延伸下来，也可能是本行新放置的芯片）。

初始时，$f[0][0][0]=0$，其他为 $-\infty$。

转移时，我们需要用第 $i$ 行和第 $i+1$ 行以及第 $i+2$ 行来放置芯片，使得第 $i$ 行被填满（因为前 $i-1$ 行已经填满，第 $i$ 行的覆盖状态 $S1$ 必须全为 1，表示所有格子都被覆盖）。但实际上，$S1$ 可能不全为 1，因为有些格子可能由上一行的芯片覆盖，有些可能由本行或下一行的芯片覆盖。所以我们需要确保在转移到 $i+1$ 时，第 $i$ 行全部被覆盖。

因此，状态设计为 $dp[i][mask]$，其中 $mask$ 是一个 $2M$ 位的二进制数，表示第 $i$ 行和第 $i+1$ 行的覆盖情况（每行 $M$ 位）。转移时，我们放置芯片，更新 $mask$，并确保第 $i$ 行在放置后全部被覆盖。

算法步骤（轮廓线 DP）

1. 读入坏块信息，构建 $bad$ 数组。
2. 预处理所有可能的芯片放置方式（包括 $2\times 3$ 和 $3\times 2$），并存储它们对三行覆盖状态的影响。
3. 使用 DP，状态 $f[i][S]$ 表示前 $i$ 行已经处理完，且第 $i+1$ 行的覆盖状态为 $S$ 时的最大芯片数。这里 $S$ 是 $M$ 位二进制，表示第 $i+1$ 行哪些格子已经被之前的芯片覆盖（从上往下延伸）。
4. 转移时，枚举在第 $i+1$ 行和第 $i+2$ 行放置芯片的所有可能方式（考虑坏块），更新状态。

由于 $M \le 10$，状态数 $2^{10}=1024$，可行。

放置方式

芯片有两种方向：

• 水平 $2\times 3$：占据两行三列。
• 垂直 $3\times 2$：占据三行两列。

当处理到第 $i$ 行时，我们考虑放置芯片的左上角位置 $(i,j)$，并检查是否合法（不超出边界、不覆盖坏块、不重叠）。

实现细节

由于芯片最大影响三行，我们需要同时维护当前行和下一行的覆盖状态。可以使用 DFS 枚举当前行放置芯片的所有可能组合，然后更新状态。

具体实现时，可以逐格递推：设 $dp[i][j][mask]$ 表示处理到第 $i$ 行第 $j$ 列，当前行和下一行的覆盖状态为 $mask$（$2M$ 位）时的最大芯片数。但这样状态数 $150\times 10\times 2^{20}$ 太大。

更优方法

由于 $M$ 很小，可以用三进制状态表示每个格子是否被覆盖以及覆盖类型，但实现复杂。

本题在《算法竞赛进阶指南》中有详细讲解，标准解法是使用状态压缩 DP，状态为当前行和上一行的覆盖情况，用 DFS 枚举当前行放置芯片的方式，并更新状态。

总结

本题是状态压缩 DP 的难题，需要仔细设计状态和转移。由于 $M \le 10$，状态压缩可行。关键是如何处理 $2\times 3$ 和 $3\times 2$ 芯片的放置，以及如何确保每行最终被完全覆盖。