2 条题解

  • 0
    @ 2025-10-22 16:19:27

    题解

    思路分析

    这是一道 插头DP（轮廓线DP） 的经典问题，需要在网格中放置 2×32 \times 3 或 3×23 \times 2 的矩形。

    问题建模

    • 在 N×MN \times M 的网格中放置 2×32 \times 3 的芯片（可旋转）
    • 某些格子被占用（原料不纯）
    • 求最多能放置多少芯片

    核心思路

    1. 插头DP状态定义

    使用轮廓线DP，状态表示当前行与上一行之间的"插头"状态。

    由于芯片是 2×32 \times 3 的，需要用四进制（0-5）表示每个格子的状态：

    • 0：未覆盖
    • 1：被芯片覆盖（单格）
    • 2：横向芯片的一部分
    • 3,4,5：不同芯片的标识

    2. 状态转移

    对于每个格子 (x,y)(x, y)，根据左边和上边的插头状态，枚举当前格子的放置方式：

    • 不放：如果左、上都未覆盖
    • 放横向芯片：需要连续3格
    • 放竖向芯片：需要连续2行

    3. 哈希优化

    由于状态数巨大，使用哈希表存储状态以节省空间。

    算法步骤

    1. 预处理：

      • 标记不可用的格子
      • 初始化DP数组

    2. 逐格DP：

      • 按行优先顺序遍历每个格子
      • 枚举所有合法的芯片放置方式
      • 更新状态

    3. 输出答案：

      • 遍历所有终止状态
      • 取最大值

    复杂度分析

    • 状态数：O(C⋅6M)O(C \cdot 6^M)，其中 CC 是状态压缩后的常数
    • 时间复杂度：O(N⋅M⋅6M)O(N \cdot M \cdot 6^M)
    • 空间复杂度：O(6M)O(6^M)

    由于 M≤10M \leq 10，复杂度可以接受。

    #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;
}
    • 0
      @ 2025-10-17 18:38:22

      题解

      将 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;
}
      • 1

      「CEOI2002」臭虫集成电路公司

      信息

      ID
      3247
      时间
      4000ms
      内存
      512MiB
      难度
      9
      标签
      递交数
      5
      已通过
      1
      上传者
      1. 评测队列
      2. 服务状态
      3. 兼容模式
      4. 主题
      2. 黔ICP备2023002402号-2
      3. Worker 0, 44ms
      4. Powered by Hydro v4.19.1 Community, Modified by 33DAI