突破状态压缩的界限：三进制与最小表示法的结合应用

核心逻辑与数学原理

在状态压缩动态规划（DP）的领域中，普通的二进制状态（17.1, 17.2）和四进制插头 DP（17.3）均基于固定基数数制（Fixed-radix Number System）。然而，当面临一些非标准网格约束、图的染色问题或带有动态容量限制的组合优化问题时，固定的二进制或四进制会导致大量的非法状态冗余（例如：用四进制表示至多三种状态，会造成大量空间无法被有效映射，常数无谓放大）。

要突破固定进制的限制，必须引入三进制状态压缩以及更高级的基于连通块映射的最小表示法（Minimal Representation）。

1. 最小表示法（Minimal Representation）的代数同构

在17.3节中，我们利用括号匹配（左括号=1，右括号=2）解决了单一回路问题。然而，如果题目要求可以绘制多条独立回路，或计算普通图染色的连通块合并（如：树的生成树计数、网格的多色连通块相连），括号表示法将完全失效。因为括号只能表达嵌套，无法表达“1号插头和3号插头属于同一个连通块，而2号和4号属于另一个连通块”这种交叉的连通拓扑。

为了消除后效性，我们必须记录轮廓线上每个插头所属的具体连通块编号。假设轮廓线从左到右有四个插头，实际连通关系为：第0、2个插头相连，第1、3个插头相连。如果直接记录为 (1, 2, 1, 2) 或 (3, 7, 3, 7)，将导致本质相同的拓扑因编号不同而被视为不同的状态。

最小表示法的核心定义：

将轮廓线上所有有插头的位置，按照从左到右第一次出现的顺序，重新从1开始连续编号。无插头的位置一律记为0。

对于上述例子，无论底层连通块的真实ID是什么，经过最小表示法重映射后，其状态掩码唯一固定为 (1, 2, 1, 2)。这种几何降维将爆炸式的集合分割数（贝尔数 Bell Number）无损压缩到极其稀疏的标量空间中。

2. 动态数制与状态编解码算子化

由于最小表示法中状态的上限取决于列数（如 $M=6$ 时，最多产生3个独立连通块，状态值最高为3），此时最完美的映射数制是三进制（Base-3）或五进制（Base-5）。

为了在考场上实现 $O(1)$ 的任意进制存取，我们需要在位运算之外，手工构建状态编解码算子网络：

• 解码（Decode）：将一个十进制整数 $S$ 拆解为行/列状态数组 code[i]。
• 编码（Encode）：将一个状态数组 code[i] 通过最小表示法规范化，并打包压回十进制整数 $S$。

状态设计与算法推导

以经典高难真题“基于连通性的网格图最小生成树（或多回路网格骨架）”为例。

1. 状态空间与编解码算子设计

设列数为 $M$。轮廓线上有 $M+1$ 个位置。定义 code 数组长度为 $M+1$。

• 解码算子 `decode(st, code)`：

  for (int i = 0; i <= m; ++i) {
    code[i] = st % 3; // 以三进制为例
    st /= 3;
  }

• 编码与最小表示法规范算子 `encode(code)`：

    int id[10], cnt = 0;
    memset(id, 0, sizeof(id));
    int st = 0;
    // 逆向打包以保证空间对称性
    for (int i = m; i >= 0; --i) {
        if (code[i] > 0) {
            if (!id[code[i]]) id[code[i]] = ++cnt; // 重新从1开始连续编号
            code[i] = id[code[i]];
        }
        st = st * 3 + code[i]; // 压入三进制
    }
    return st;

2. 状态转移中的连通块重组（重连算子化）

逐格 $(i, j)$ 推进时，提取左插头 $L = code[j-1]$，上插头 $U = code[j]$：

• 若 $L > 0$ 且 $U > 0$ 且 $L eq U$：说明两条原本独立的连通块在此处接头。执行**全图染色合并**：遍历整个 `code` 数组，将所有等于 $U$ 的插头强制批量改写为 $L$。
• 若某一时刻某个连通块被彻底从 code 数组里抹去了（即没有任何一个轮廓线插头再带有这个编号）：必须严格校验这是否是全图的最后一个连通块。如果是，则属于合法收尾；如果图还未走完，这个连通块就已经提前在轮廓线上消失，说明它在未来再也无法连通，整棵生成树会断裂成森林，该状态必须立刻强行剪枝抛弃。

C++ 标准源码（NOIP/省选终极状压通用模板）

以下源码演示了利用最小表示法和动态三进制进行网格全连通块路径覆盖（骨架提取）的标准工业实现，支持大常数榨干优化。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int HASH_SIZE = 30007; // 选用大质数抵抗冲突
const int MAX_STATES = 200005;

int n, m;
int maze[12][12];
int code[15], temp_code[15];

struct HashTable {
    int head[HASH_SIZE], next[MAX_STATES], size;
    int state[MAX_STATES];
    long long value[MAX_STATES];

    void clear() {
        size = 0;
        memset(head, -1, sizeof(head));
    }

    void insert(int st, long long val) {
        int key = st % HASH_SIZE;
        for (int i = head[key]; i != -1; i = next[i]) {
            if (state[i] == st) {
                value[i] = max(value[i], val); // 此处以求最大权值/方案为例
                return;
            }
        }
        state[size] = st;
        value[size] = val;
        next[size] = head[key];
        head[key] = size++;
    }
} ht[2];

// 核心算子：解码
void decode(int st) {
    for (int i = 0; i <= m; ++i) {
        code[i] = st % 3;
        st /= 3;
    }
}

// 核心算子：最小表示法规范化并编码
int encode() {
    int id[15], cnt = 0;
    memset(id, 0, sizeof(id));
    int st = 0;
    for (int i = m; i >= 0; --i) {
        if (code[i] > 0) {
            if (!id[code[i]]) id[code[i]] = ++cnt;
            code[i] = id[code[i]];
        }
        st = st * 3 + code[i];
    }
    return st;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> maze[i][j]; // 1表示空格，0表示障碍
        }
    }

    int cur = 0;
    ht[cur].clear();
    ht[cur].insert(0, 0); // 初始全0状态

    for (int i = 1; i <= n; ++i) {
        // 跨行时，轮廓线平移：所有插头向右移动一格，最左侧补0
        for (int k = 0; k < ht[cur].size; ++k) {
            decode(ht[cur].state[k]);
            for (int l = m; l >= 1; --l) code[l] = code[l - 1];
            code[0] = 0;
            ht[cur].state[k] = encode();
        }

        for (int j = 1; j <= m; ++j) {
            int nxt = cur ^ 1;
            ht[nxt].clear();

            for (int k = 0; k < ht[cur].size; ++k) {
                int st = ht[cur].state[k];
                long long val = ht[cur].value[k];

                decode(st);
                int p_left = code[j - 1]; // 左插头
                int p_up = code[j];       // 上插头

                if (!maze[i][j]) {
                    // 障碍物格子：强制两引脚必须为0才能放行
                    if (p_left == 0 && p_up == 0) {
                        ht[nxt].insert(st, val);
                    }
                    continue;
                }

                // 核心分支 A：左右皆无插头输入 -> 凭空创建新的独立连通块
                if (p_left == 0 && p_up == 0) {
                    if (maze[i][j + 1] && maze[i + 1][j]) {
                        code[j - 1] = code[j] = 2; // 临时赋予一个未使用的独立大编号
                        ht[nxt].insert(encode(), val + 1); // 假设权值为边数
                    }
                }
                // 核心分支 B：单插头流入 -> 延续拓扑
                else if (p_left == 0 || p_up == 0) {
                    int p_val = p_left ? p_left : p_up;
                    if (maze[i][j + 1]) { // 延续向右
                        code[j - 1] = 0; code[j] = p_val;
                        ht[nxt].insert(encode(), val + 1);
                    }
                    decode(st); // 重置状态数组，进行第二种分支决策
                    if (maze[i + 1][j]) { // 延续向下
                        code[j - 1] = p_val; code[j] = 0;
                        ht[nxt].insert(encode(), val + 1);
                    }
                }
                // 核心分支 C：两插头流入且属于不同连通块 -> 执行强连通块染色合并
                else if (p_left > 0 && p_up > 0 && p_left != p_up) {
                    int src = p_up, dst = p_left;
                    for (int l = 0; l <= m; ++l) {
                        if (code[l] == src) code[l] = dst; // 批量大染色
                    }
                    code[j - 1] = code[j] = 0; // 当前格汇合消亡
                    ht[nxt].insert(encode(), val + 1);
                }
                // 核心分支 D：两插头流入且本身就属于同一个连通块 -> 闭合回路判定
                else if (p_left > 0 && p_up > 0 && p_left == p_up) {
                    code[j - 1] = code[j] = 0;
                    int remaining_blocks = 0;
                    int check_st = encode();
                    // 检查轮廓线上是否还有其他残留插头
                    if (check_st == 0) {
                        // 彻底闭合且全图无其他连通块，属于完美终局解
                        ht[nxt].insert(0, val + 1);
                    }
                }
            }
            cur = nxt;
        }
    }

    // 收集最终彻底闭合成唯一连通块（状态为0）的最大收益
    long long ans = 0;
    for (int k = 0; k < ht[cur].size; ++k) {
        if (ht[cur].state[k] == 0) {
            ans = max(ans, ht[cur].value[k]);
        }
    }

    cout << ans << "\n";
    return 0;
}

NOIP/省选 实战避坑指南

1. 编码时遗漏 code 数组的清空重组（脏数据残留污染）

• 现象：在分支决策中，选手直接修改了 code[j-1] 和 code[j]，但在进入下一个循环迭代或生成新状态插入时，由于没有完全对整条轮廓线进行重新编码洗牌，导致上一次大染色合并后的旧连通块编号以脏数据的形式残留在内存中。这会引起状态冲突校验大面积误判，直接导致 WA（答案错误）。
• 规避手段：在每一个状态决策完毕、准备执行 encode() 之前，必须严格重新规范化编号（如源码中利用 id 数组实现重新从1开始贴标签）。

2. 忽略孤立连通块提早非正常消亡的判定（森林断裂漏洞）

• 现象：在分支转移中，两条路径汇合导致某个连通块编号从轮廓线上彻底清零。此时若不加校验就直接把该状态扔进哈希表，会产生“中间产生了一个独立的闭合环，而外部其他地方还在继续画线”的惨剧。对于要求“全图必须构成单一连通图（如生成树）”的题目，这种漏洞会导致算出来的结果远远大于正确答案。
• 规避手段：任何时候只要有编号消失，必须立刻横向扫描 code 数组中是否还存在任何大于0的元素。若存在其他元素，说明此消亡是非法的提早断路，必须直接 continue 剪枝。

经典省选/NOI 真题

1. 洛谷 P4262 [CodeChef] 白白白 / [网络流24题] 方格取数进阶

• 题意描述：给定一个 $N \times M$ 的方格图，每个格点有不同的类型。要求在网格中放置若干条互不相交的路径，使得覆盖的格点总权重最大。$N \le 12, M \le 12$。
• 问题本质与解题思路：基于连通性多路径覆盖的最小表示法状压。
• 核心思路：由于路径不要求闭合成单回路（可以有多个独立段），括号表示法无法记录断头的配对关系。必须使用最小表示法：
• 状态 0：无插头。
• 状态 1、2、3：代表不同端点连通块的 ID。在格子内部，除了对接，还可以选择“在这里作为路径的起点或终点终止”。利用三进制/五进制在哈希表里滚动更新，即可在规定时限内完美斩获满分。

2. 洛谷 P2434 [SDOI2008] 烧香 / 丛林路线

• 题意描述：在 $N \times M$ 的丛林网格中，某些地方可以通行。要求铺设一条不自交、不重复且能连通指定起点和终点的丛林轨道，求最大可铺设的轨道总长度。$N \le 10, M \le 10$。
• 问题本质与解题思路：指定源汇点的最大全连通路径提取。
• 核心思路：属于插头 DP 与最小表示法的高维结合体。相比普通的无向回路，本题在初始化和终局判定时，必须对指定的“起点格子”和“终点格子”注入强前驱插头约束（即这两个格子天然拥有一个指向图外的外部插头）。在中间转移时，利用最小表示法严格控制除主干连通块外，不能产生任何独立的寄生小环。当扫描到指定终点且轮廓线其余插头全部收敛为0时，触发最终最优解的收集。