题目描述
设有 (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)) 时的最大得分。
本题建模
转移方程
从 (k-1) 步转移到 (k) 步时，每条路径有两种选择：上一步在「上方格子」（向下走）或「左方格子」（向右走）。两条路径各有两种选择，共 (2 \times 2 = 4) 种组合：
转移方程：
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) 的方格图如下：
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;
}本地验证
本地编译运行样例：
\( g++ -o p1004 p1004.cpp
\) ./p1004 < sample.in
洛谷验证
提交到洛谷评测系统，评测结果：
全部测试点通过。
调试记录
坑一：(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）都可以用相同技巧。
这种状态压缩技巧在竞赛中很常见：当多个对象的运动存在某种同步约束时，利用该约束减少状态维度。
交互模拟器
在下方模拟器中逐步观察 DP 状态转移矩阵的构建过程：