第2题-双通道评测格网

小红书9月10日机考题目与解析

给定一张 $N$ 行 $M$ 列的评测格网。格子 $(i,j)$ 上有两个通道分 $X{i,j}$ 与 $Y{i,j}$。

从 $(1,1)$ 走到 $(N,M)$，每次只能向右走到 $(i,j+1)$ 或向下走到 $(i+1,j)$，不可越界。

路径上每个格子（含起终点）须把 $X{i,j}$ 与 $Y{i,j}$ 分别记入主账户与对照账户，二者各得其一。

设主账户合计为 $S$，对照账户合计为 $T$。求所有合法路径与分配方案下 $|S - T|$ 的最小值。

输入描述

输入共 $2N+1$ 行。第一行两个整数 $N$ 和 $M$；接下来 $N$ 行每行 $M$ 个整数，表示 $X{i,j}$；再接下来 $N$ 行每行 $M$ 个整数，表示 $Y{i,j}$。

数据范围：$1 \le N, M \le 80$，$0 \le X{i,j}, Y{i,j} \le 80$。

输出描述

输出一行一个整数，即最小的 $|S - T|$。

样例 1

输入：

2 2
4 1
2 5
2 3
6 1

输出：

0

说明：路径 $(1,1) \to (1,2) \to (2,2)$。$(1,1)$：主账户记 $2$，对照账户记 $4$；$(1,2)$：主账户记 $1$，对照账户记 $3$；$(2,2)$：主账户记 $5$，对照账户记 $1$。此时 $S=8$，$T=8$，$|S-T|=0$。另一条路径 $(1,1) \to (2,1) \to (2,2)$ 上，$|S-T|$ 至少为 $2$，更差。

思路

路径 DP + 可达集合（bitset）。每个格子的贡献是 $\pm d_{ij}$（$d = X - Y$：$X$ 记主账户得 $+d$，$Y$ 记主账户得 $-d$），问题变成：路径上给每个 $d$ 选符号，最小化总和的绝对值。

用 DP 维护「走到 $(i,j)$ 时所有可达差值」的集合。路径长度 $N+M-1 \le 159$、数值 $\le 80$，差值范围 $[-12720, 12720]$，把集合编码成一个大整数的位掩码（第 $\text{diff}+\text{OFF}$ 位为 1 表示可达），转移只需一次移位：

$$\text{dp}[i][j] = (\text{cur} \ll |d_{ij}|)\ \vert\ (\text{cur} \gg |d_{ij}|)$$

其中 cur = dp[i-1][j] | dp[i][j-1]（向右/向下两来源合并）。Python 大整数位运算一次处理整个集合，复杂度约 $O(NM \cdot R / w)$（$R$ 为差值范围，$w$ 为机器字长），远快于逐值布尔 DP。

代码

n, m = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(n)]
Y = [list(map(int, input().split())) for _ in range(n)]

L = n + m - 1
OFF = 80 * L + 1     # 差值偏移，覆盖最坏 ±80*L

dp = [[0] * m for _ in range(n)]
d00 = abs(X[0][0] - Y[0][0])
dp[0][0] = (1 << (OFF + d00)) | (1 << (OFF - d00))

for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            continue
        cur = 0
        if i > 0:
            cur |= dp[i - 1][j]
        if j > 0:
            cur |= dp[i][j - 1]
        e = abs(X[i][j] - Y[i][j])
        dp[i][j] = (cur << e) | (cur >> e)

mask = dp[n - 1][m - 1]
k = 0
while not ((mask >> (OFF + k)) & 1) and not ((mask >> (OFF - k)) & 1):
    k += 1
print(k)