G. 网格优化 题解

---

1. 题意回顾

有一个 $n \times n$ 的网格图，从 $(1,1)$ 出发，只能向右或向下走，最终到达 $(n,n)$。

• 向下走的边：从 $(x,y)$ 到 $(x+1,y)$，边权为 $d_{x,y}$（$1 \le x < n$，$1 \le y \le n$）
• 向右走的边：从 $(x,y)$ 到 $(x,y+1)$，边权为 $r_{x,y}$（$1 \le x \le n$，$1 \le y < n$）

路径经过的边权会被收集到一个集合 $S$ 中。
目标：最大化 $S$ 的 $\operatorname{MEX}$。

$\operatorname{MEX}$ 是不属于 $S$ 的最小非负整数。

约束：$n \le 20$，所有测试用例的 $n^3$ 之和 $\le 8000$，边权在 $[0, 2n-2]$ 范围内。

---

2. 关键观察

观察 1：
如果 $\operatorname{MEX} = k$，说明 $0, 1, 2, \dots, k-1$ 都出现在 $S$ 中，而 $k$ 不在 $S$ 中。
因此，我们想判断：能否找一条路径，使得它包含 $0,1,\dots,k-1$ 中的所有数，但不包含 $k$？

观察 2：
由于边权范围是 $0 \le w \le 2n-2$，而路径长度固定为 $2n-2$ 条边（因为从 $(1,1)$ 到 $(n,n)$ 必须向下走 $n-1$ 步，向右走 $n-1$ 步），所以 $S$ 的大小恰好是 $2n-2$。

这意味着 $S$ 中元素个数是固定的：$|S| = 2n-2$。

观察 3：
如果 $\operatorname{MEX} = k$，那么 $S$ 必须包含 $0,1,\dots,k-1$ 这 $k$ 个不同的数。由于 $|S| = 2n-2$，必须有 $k \le 2n-2$。
另外，$S$ 中不能包含 $k$。

因此，问题等价于：对于每个 $k$，判断是否存在一条路径，使得：

• 所有 $0,1,\dots,k-1$ 都至少出现一次；
• $k$ 不出现。

---

3. 数据范围分析

$n \le 20$，路径长度 $2n-2 \le 38$，边权范围 $[0, 2n-2] \le 38$。
这个范围非常小，适合用 状态压缩动态规划。

我们可以用 位掩码 表示某个数值集合是否已经出现过。

设 $f[i][j][mask]$ 表示：从 $(1,1)$ 走到 $(i,j)$ 时，已经收集到的数值集合为 $mask$ 是否可达。

但这样状态数太多：
$n^2 = 400$，$mask$ 的范围是 $2^{2n-1}$，当 $n=20$ 时 $2^{39}$ 太大，不可行。

---

4. 优化：二分答案 + 可行性判断

因为 $\operatorname{MEX}$ 最大为 $2n-1$，我们可以 二分答案：

判断是否存在一条路径，使得 $\operatorname{MEX} \ge k$，即 $0,1,\dots,k-1$ 全部出现在 $S$ 中。

此时我们只需要关心这 $k$ 个数是否都出现过，其他数不影响（只要不包含 $k$ 即可，但二分时我们只要求 $0..k-1$ 全出现，不限制 $k$ 是否出现，因为二分的是下界）。

---

5. 可行性 DP

对于固定的 $k$，我们只关心 $0,1,\dots,k-1$ 这 $k$ 个数是否出现，其他数统一视为“无关”。

状态压缩：用一个 $k$ 位二进制数 $mask$ 表示 $0..k-1$ 中哪些数已经出现过。

状态：$dp[i][j][mask]$ 表示从 $(1,1)$ 走到 $(i,j)$ 时，已经收集到的数值集合为 $mask$ 是否可达。

转移：从 $(i,j)$ 向右或向下走，遇到边权 $w$：

• 如果 $w < k$，则新 $mask' = mask \mid (1 \ll w)$；
• 如果 $w \ge k$，则 $mask' = mask$（不影响 $0..k-1$ 的收集情况）。

初始状态：$dp[1][1][0] = \text{true}$（初始集合为空）。

最终判断：是否存在 $mask$ 使得 $dp[n][n][mask]$ 为真且 $mask$ 包含了所有 $k$ 位（即 $mask = (1 \ll k) - 1$）。

---

6. 复杂度分析

对于固定的 $k$，状态数：$n^2 \times 2^k$。
枚举 $n=20$，$k$ 最大 $39$，$2^{39}$ 太大。
但 $k$ 实际上不会很大，因为 $S$ 只有 $2n-2$ 个元素，而 $0..k-1$ 需要 $k$ 个不同的数，所以 $k \le 2n-2 = 38$。
但 $2^{38}$ 仍然太大（$2.7 \times 10^{11}$），不可行。

---

7. 进一步优化：meet-in-the-middle

由于 $n \le 20$，路径长度 $2n-2 \le 38$，我们可以将路径分成两半：

• 前半段：从 $(1,1)$ 到某个中间位置（如所有满足 $x+y = n+1$ 的点，即反对角线）。
• 后半段：从该中间位置到 $(n,n)$。

枚举所有前半段路径，收集它们得到的数值集合（用位掩码表示）。
然后枚举所有后半段路径，看能否和某个前半段拼接成完整路径，使得 $0..k-1$ 全部出现。

这样状态数大大减少：前半段路径条数大约为 $\binom{2n-2}{n-1}$，当 $n=20$ 时约为 $\binom{38}{19} \approx 3.5 \times 10^{10}$，仍然太大，不可直接枚举。

---

8. 实际可行解法（官方做法）

由于 $n \le 20$ 且边权范围小，官方解法采用 折半枚举 结合 哈希 / 位压缩：

1. 将路径分成两段：从起点到中间对角线，再从中间对角线到终点。
2. 枚举前半段的所有路径（最多 $\binom{n-1}{\lfloor (n-1)/2 \rfloor}$ 条，当 $n=20$ 时约为 $\binom{19}{9} \approx 92378$，可行）。
3. 对每条前半段路径，记录它收集到的数值集合 $mask1$ 和它的结束位置 $(i,j)$（满足 $i+j = n+1$）。
4. 对每条后半段路径，记录它收集到的数值集合 $mask2$ 和它的起始位置（同样在 $i+j = n+1$ 上）。
5. 对于每个中间位置，检查是否存在前半段和后半段使得 $mask1 \mid mask2$ 包含 $0..k-1$ 的全部。

这就是 meet-in-the-middle + 位掩码。

---

9. 二分答案 + meet-in-the-middle 算法步骤

1. 读入 $d$ 和 $r$ 矩阵。
2. 预处理所有从 $(1,1)$ 到对角线 $x+y = n+1$ 的路径，记录每条路径的：
   • 终点 $(x,y)$（满足 $x+y = n+1$）
   • 收集到的数值集合 $mask$（用一个 $2n-1$ 位的整数表示，但实际只需 $2n-1 \le 39$ 位）
3. 预处理所有从对角线 $x+y = n+1$ 到 $(n,n)$ 的路径，记录每条路径的：
   • 起点 $(x,y)$
   • 收集到的数值集合 $mask$
4. 对每个 $k$ 从 $0$ 到 $2n-1$ 二分：
   • 对于每个中间位置，检查是否存在 $mask1$ 和 $mask2$ 使得 $(mask1 \mid mask2)$ 包含 $0..k-1$。
   • 可用哈希表或按位置分组优化。
5. 找到最大的 $k$ 使得存在这样的路径。

---

10. 最终答案

最大可能的 $\operatorname{MEX}$ 不会超过 $2n-1$，因为 $S$ 大小只有 $2n-2$，最多能包含 $0..2n-3$，所以 $\operatorname{MEX} \le 2n-2$ 或 $2n-1$？

实际上，如果 $S$ 恰好包含 $0..2n-3$，则 $\operatorname{MEX} = 2n-2$，不可能达到 $2n-1$（因为那样需要包含 $0..2n-2$ 共 $2n-1$ 个数，但只有 $2n-2$ 条边）。

所以答案范围是 $0 \le \text{ans} \le 2n-2$。

---

11. 复杂度

• 枚举前半段路径：$O(\binom{n-1}{\lfloor (n-1)/2 \rfloor} \cdot (n-1))$
• 枚举后半段路径：$O(\binom{n-1}{\lfloor (n-1)/2 \rfloor} \cdot (n-1))$
• 二分答案 $O(\log n)$
• 总复杂度：$O(\binom{n-1}{\lfloor (n-1)/2 \rfloor} \cdot n \cdot \log n)$，当 $n=20$ 时约 $9 \times 10^4 \times 20 \times 5 \approx 10^7$，可接受。

---

12. 核心代码框架

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> d, r;

// 对角线上的点：x + y = n + 1
vector<vector<int>> diag;  // diag[pos] 存储该点信息

// 枚举所有从 (1,1) 到对角线 x+y=mid+1 的路径
void dfs1(int x, int y, int mask, int len, vector<unordered_map<int,bool>>& dp1) {
    if (x + y == n + 1) {
        dp1[(x-1)*n + (y-1)][mask] = true;
        return;
    }
    // 向下走
    int w = d[x][y];
    int nmask = mask | (1 << w);
    dfs1(x+1, y, nmask, len+1, dp1);
    // 向右走
    w = r[x][y];
    nmask = mask | (1 << w);
    dfs1(x, y+1, nmask, len+1, dp1);
}

// 类似地枚举后半段路径...

bool check(int k) {
    // 判断能否收集到 0..k-1
    int target = (1 << k) - 1;
    for (int mid = 0; mid < diag.size(); mid++) {
        for (auto& [mask1, _] : dp1[mid]) {
            for (auto& [mask2, _] : dp2[mid]) {
                if ((mask1 | mask2) == target) return true;
            }
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        d.assign(n+1, vector<int>(n+1));
        r.assign(n+1, vector<int>(n+1));
        // 读入 d 矩阵 (n-1 行)
        for (int i = 1; i <= n-1; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> d[i][j];
            }
        }
        // 读入 r 矩阵 (n 行)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n-1; j++) {
                cin >> r[i][j];
            }
        }

        // meet-in-the-middle 预处理
        vector<unordered_map<int,bool>> dp1(n*n), dp2(n*n);
        dfs1(1, 1, 0, 0, dp1);
        // 从 (n,n) 反向 dfs 到对角线...
        // 然后二分答案

        int lo = 0, hi = 2*n-2;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (check(mid)) lo = mid;
            else hi = mid - 1;
        }
        cout << lo << "\n";
    }
    return 0;
}