题解

将 2×3 Q-RAM 芯片的贴合过程转化成宽度为 m 的逐行状态 DP。对每一行，我们用长度为 m 的状态数组描述这一行各列当前的“悬空”形态（六种情况用 0~5 编号，分别代表该列是否被芯片覆盖、是否需要和下一行/上一行配对等），dfs_c 会枚举所有满足局部奇偶约束的行状态并存入 va，同时用 mask 记录这一行哪些格子被占用。check(state, row) 用位运算判定某状态能否放在给定行上，而 isp(x, y) 则给出两个相邻状态在同一列上的合法组合关系，只有上下两行在每一列拼成合法的 2×3 形状时才允许转移。

预处理完所有状态后，预先构建状态图 trans，然后按行自上而下做 DP：f[i][state] 表示处理到第 i 行且当前行使用 state 时最多能切出的芯片数量。转移时遍历所有能跟上一行状态拼接的 state，用 th 统计编号为 3 的格子（需要两行合并）完成的芯片数量，用 fv 统计编号为 5 的格子（三行合并）的贡献，并把它们累加到下一行的答案中。所有禁止的格子在 check 时被跳过。最终在第 n 行求得的最大值，就是整块硅片能够切出的 Q-RAM 芯片数量。

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
int n, m, k;
int a[150][10];
vector<int> chos;
vector<vector<int>> va;
vector<int> trans[5779];
int mask[5799];
int full[150];
int f[2][5779];
bool check(int cid, int id)
{
    if ((mask[cid] | full[id]) != full[id])
        return 0;
    if (!id)
    {
        for (int i = 0; i < m; i++)
        {
            if (va[cid][i] != 4 && va[cid][i] != 1 && va[cid][i] != 0)
                return 0;
        }
    }
    return 1;
}
bool isp(int x, int y)
{
    return (x == 0 && y == 0) ||
           (x == 0 && y == 1) ||
           (x == 0 && y == 4) ||
           (x == 1 && y == 2) ||
           (x == 2 && y == 3) ||
           (x == 3 && y == 0) ||
           (x == 3 && y == 1) ||
           (x == 3 && y == 4) ||
           (x == 4 && y == 5) ||
           (x == 5 && y == 0) ||
           (x == 5 && y == 1) ||
           (x == 5 && y == 4);
}
void dfs_c(int dep)
{
    if (dep == m)
    {
        int cnt[6] = {};
        cnt[chos[0]]++;
        for (int i = 1; i <= m; i++)
        {
            if (chos[i] != chos[i - 1] || i == m)
            {
                if (cnt[1] % 2 || cnt[2] % 2 || cnt[3] % 2 || cnt[4] % 3 || cnt[5] % 3)
                    return;
                memset(cnt, 0, sizeof(cnt));
            }
            if (i < m)
                cnt[chos[i]]++;
        }
        va.push_back(chos);
        return;
    }
    if (dep)
    {
        if (1 <= chos[dep - 1] && chos[dep - 1] <= 3)
        {
            if (dep == 1 || chos[dep - 1] != chos[dep - 2])
            {
                chos[dep] = chos[dep - 1];
                dfs_c(dep + 1);
                return;
            }
        }
        if (4 <= chos[dep - 1] && chos[dep - 1] <= 5)
        {
            if (dep == 1 || chos[dep - 1] != chos[dep - 2])
            {
                chos[dep] = chos[dep - 1];
                dfs_c(dep + 1);
                return;
            }
        }
    }
    for (int i = 0; i < 6; i++)
        chos[dep] = i, dfs_c(dep + 1);
}
void solve()
{
    cin >> n >> m >> k;
    chos.resize(m);
    va.clear();
    for (int i = 0; i < 5779; i++)
        trans[i].clear();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            a[i][j] = 1;
    }
    while (k--)
    {
        int x, y;
        cin >> x >> y;
        a[x - 1][y - 1] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            (full[i] <<= 1) |= a[i][j];
    }
    dfs_c(0);
    // cout << va.size() << '\n';
    for (int i = 0; i < va.size(); i++)
    {
        mask[i] = 0;
        for (int j : va[i])
            (mask[i] <<= 1) |= (j > 0);
    }
    for (int i = 0; i < va.size(); i++)
    {
        for (int j = 0; j < va.size(); j++)
        {
            bool ok = 1;
            for (int k = 0; k < m; k++)
            {
                if (!isp(va[i][k], va[j][k]))
                {
                    ok = 0;
                    break;
                }
            }
            if (ok)
                trans[i].push_back(j);
        }
    }
    int ans = 0;
    int t = 0;
    memset(f[t], -1, sizeof(f[t]));
    for (int i = 0; i < va.size(); i++)
    {
        if (check(i, 0))
            f[t][i] = 0;
    }
    for (int i = 1; i < n; i++)
    {
        t ^= 1;
        memset(f[t], -1, sizeof(f[t]));
        for (int j = 0; j < va.size(); j++)
        {
            if (f[t ^ 1][j] == -1)
                continue;
            for (int k : trans[j])
            {
                if (!check(k, i))
                    continue;
                // cout << i << " " << j << " " << k << endl;
                int th = 0, fv = 0;
                for (int col : va[k])
                {
                    if (col == 3)
                        th++;
                    if (col == 5)
                        fv++;
                }
                th /= 2, fv /= 3;
                chkmx(f[t][k], f[t ^ 1][j] + th + fv);
                chkmx(ans, f[t][k]);
            }
        }
    }
    cout << ans << endl;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}