题目描述

设有 $N \times N$ 的方格图（$N \le 9$），某些方格中填入正整数，其余填入 $0$。某人从左上角 $A$ 出发，只能向右或向下走，到达右下角 $B$。在走过的路上，他可以取走方格中的数（取走后该方格变为 $0$）。此人共走两次，试找出 $2$ 条路径，使得取得的数之和最大。

输入格式：第一行 $N$，随后每行三个整数 $x, y, v$ 表示坐标 $(x,y)$ 处填有 $v$，以 $0\ 0\ 0$ 结束。

读题分析

乍看之下，这道题要求「两条路径」，很自然会想到枚举第一条路径、再对第二条路径 DP 或搜索。但这样做有两个问题：

第一条路径的组合数极大（枚举量太大，$N=9$ 时约 $48620$ 种走法）。
两条路径经过同一个格子时，该格子的值只能被取一次——这是本题的难点，也是算法设计的核心约束。

为什么不能简单拆成两次独立的最优路径？

如果两次走同一条最优路径，第二次经过的格子值全为 $0$，收益为零。如果走两条不同的路径，又需要协调两条路径的「重合度」。这说明两条路径不是独立的，必须同时决策。

算法分析

朴素四维 DP

最自然的想法是定义：

$$dp[x_1][y_1][x_2][y_2]$$

表示路径一到达 $(x_1,y_1)$、路径二到达 $(x_2,y_2)$ 时的最大得分。

状态数 $O(N^4)$，每个状态有 $2 \times 2 = 4$ 个转移来源，总复杂度 $O(N^4)$。当 $N \le 9$ 时 $N^4 = 6561$，完全可以接受。

但这里有一个隐含约束可以让状态降维。

状态压缩：四维 → 三维

关键观察： 两条路径都从 $(1,1)$ 出发，每次只能向右或向下走。从 $(1,1)$ 到达 $(x,y)$ 恰好需要 $(x-1) + (y-1) = x+y-2$ 步。因此，当两条路径走了相同步数时，$x_1+y_1 = x_2+y_2$。

设 $k = x_1+y_1 = x_2+y_2$，则 $y_1 = k-x_1$，$y_2 = k-x_2$。我们只需要记录 $k, x_1, x_2$，状态从四维压缩为三维：

$$dp[k][x_1][x_2]$$

表示两条路径各走了 $k$ 步，分别位于 $(x_1, k!-!x_1)$ 和 $(x_2, k!-!x_2)$ 时的最大得分。

图 1：状态压缩过程。利用 $x_1+y_1=x_2+y_2$ 的隐含约束，从四维降为三维。

本题建模

转移方程

从 $k-1$ 步转移到 $k$ 步时，每条路径有两种选择：上一步在「上方格子」（向下走）或「左方格子」（向右走）。两条路径各有两种选择，共 $2 \times 2 = 4$ 种组合：

图 2：四个前驱状态，对应两条路径各自从上或从左到达当前位置的四种组合。

转移方程：

dp[k][x₁][x₂] = max(四个前驱) + 当前格子得分

其中四个前驱状态为：

$dp[k!-!1][x_1!-!1][x_2!-!1]$: 两人均从上一步的上/上位置来
$dp[k!-!1][x_1][x_2]$: 两人均从左/左位置来
$dp[k!-!1][x_1!-!1][x_2]$: P1 从上, P2 从左
$dp[k!-!1][x_1][x_2!-!1]$: P1 从左, P2 从上

当前格子得分：$a[x_1][y_1]$，若 $x_1 \neq x_2$ 则再加 $a[x_2][y_2]$。

注意： 当 $x_1 = x_2$ 时，两条路径经过同一个格子（因为 $y_1 = k-x_1 = k-x_2 = y_2$），该格子的值只能被计算一次。

样例展示

以洛谷官方样例为例，$8 \times 8$ 的方格图如下：

图 3：样例方格图。橙色和蓝色两条路径同时从 A 走到 B，最优答案由 DP 计算得出。

DP 执行流程

图 4：完整的 DP 执行流程：读入 → 初始化 → 枚举步数 → 转移 → 输出。

代码实现

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

const int N = 12;
int a[N][N];
int f[N * 2][N][N]; // f[step][x1][x2]

int main() {
    int n;
    scanf("%d", &n);

    int x, y, v;
    while (true) {
        scanf("%d%d%d", &x, &y, &v);
        if (x == 0 && y == 0 && v == 0) break;
        a[x][y] = v;
    }

    // f[k][i][j] = max score when:
    //   person 1 is at (i, k-i) and person 2 is at (j, k-j)
    memset(f, 0, sizeof(f));

    for (int k = 2; k <= 2 * n; k++) {
        for (int i = 1; i <= n; i++) {
            int j1 = k - i;
            if (j1 < 1 || j1 > n) continue;
            for (int j = 1; j <= n; j++) {
                int j2 = k - j;
                if (j2 < 1 || j2 > n) continue;

                // Previous positions (4 combinations):
                // 1) both from above: (i-1, j-1) at step k-1
                // 2) both from left: (i, j) at step k-1
                // 3) p1 from above, p2 from left: (i-1, j)
                // 4) p1 from left, p2 from above: (i, j-1)
                int prev = 0;
                if (k > 2) {
                    prev = max(f[k-1][i-1][j-1], f[k-1][i][j]);
                    prev = max(prev, f[k-1][i-1][j]);
                    prev = max(prev, f[k-1][i][j-1]);
                }

                int val = a[i][j1];
                if (i != j) val += a[j][j2];
                f[k][i][j] = prev + val;
            }
        }
    }

    printf("%d\n", f[2*n][n][n]);
    return 0;
}

调试记录

坑一：$x_1 = x_2$ 时格子值重复计算

第一次写代码时，不管 $x_1$ 是否等于 $x_2$，都直接加 $a[x_1][y_1] + a[x_2][y_2]$。当两条路径经过同一个格子时，该格子值被算了两次，导致答案偏大。

修复： 加判断 if (i != j) val += a[j][j2];。

坑二：边界检查遗漏

枚举 $x_1, x_2$ 时，没有检查对应的 $y_1 = k-x_1$ 是否在 $[1, n]$ 范围内，导致访问越界。

修复： 加 if (j1 < 1 || j1 > n) continue;。

坑三：$k=2$ 时无前驱

当 $k=2$ 时（两条路径都在起点 $(1,1)$），没有前驱状态。如果直接访问 f[1][...] 会读取未初始化的内存。

修复： 加 if (k > 2) 判断，$k=2$ 时 prev = 0。

复杂度分析

时间复杂度： $O(N^3)$。枚举 $k \in [2, 2N]$（$O(N)$），每个 $k$ 枚举 $x_1, x_2 \in [1, N]$（$O(N^2)$），每次转移 $O(1)$。
空间复杂度： $O(N^3)$。三维 DP 表 $f[2N][N][N]$。

当 $N \le 9$ 时，状态数约 $18 \times 9 \times 9 = 1458$，完全可接受。

总结

这道题的关键在于三个洞察：

两条路径的步数约束——$x_1+y_1 = x_2+y_2$ 是隐含但至关重要的约束，将四维 DP 压缩为三维。
同一格子的去重——两条路径经过相同格子时，值只算一次，需要显式判断 $x_1 \neq x_2$。
四维 DP 到三维压缩的通用模式——这类「双路径同步遍历」的问题（如「传纸条」P1006）都可以用相同技巧。

这种状态压缩技巧在竞赛中很常见：当多个对象的运动存在某种同步约束时，利用该约束减少状态维度。

P1004 方格取数