形式化题目

给定 $N \times N$ 网格，部分格子放有正整数（其余格子为 0）。从左上角 $A=(1,1)$ 出发，每步只能向下或向右，走到右下角 $B=(N,N)$；沿途可以取走格子里的数，取走后该格变为 0。同一路径走两次（两条路径独立选择），求两次取数之和的最大值。

• 关键约束：两条路径踩到同一格时，该格的数只计一次（因为已被取走）。
• 数据范围：$N \leqslant 9$（真实数据出现过 $N=10$），权值为正整数。

样例的最优方案如下表：① 标记第一条路径，② 标记第二条路径，格子显示权值。第一条路径取到 $(2,3)=13$、$(4,4)=14$、$(5,6)=4$ 共 31；第二条取到 $(5,2)=21$、$(6,3)=15$ 共 36；两条在起点、$(1,2)$ 与末段 $(6,8),(7,8),(8,8)$ 重合，这些格子权值为 0（或只被取一次），总和 $31 + 36 = 67$。

注意第 7 行的 14 不在任何一条最优路径上——单条路径“路过最多”不等于两条路径“合起来取最多”，选路必须把两条路径放在一起权衡。

正解

思路

朴素做法与其瓶颈。 最直接的想法是枚举路径：$N=9$ 时共有 $C(16,8)=12870$ 条路径，两两配对约 $8 \times 10^7$ 对，每对还要扫描重叠，太慢。另一种直觉是“先做一次单路径最大和 DP，把走过的格子清 0，再做一次”——这是错的：第一条的局部最优会抢占第二条需要的高值格子。真实数据 fgqs2 上两次贪心只得 23 而最优是 25；最小反例是 $N=3$、非零格 $(1,3){=}1,\ (2,1){=}7,\ (2,2){=}4,\ (2,3){=}3,\ (3,1){=}3,\ (3,2){=}5,\ (3,3){=}3$：第一遍走 $(1,1)\to(2,1)\to(2,2)\to(3,2)\to(3,3)$ 得 19，把该路径上的格子（含终点）清零后第二遍最优只剩 4（走 $(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)$），合计 23；而最优方案是“$(1,1)\to(1,2)\to(2,2)\to(2,3)\to(3,3)$ 取 $4+3+3=10$”加上“$(1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)$ 取 $7+3+5=15$”（重叠的终点 $(3,3)$ 只计一次），合计 25。问题的本质是两条路径必须联合决策，先后次序不最优。

关键观察：两条路径等长，可以按步同步。 无论怎么走，每条路径都恰好走 $2(N-1)$ 步（$N-1$ 次下 + $N-1$ 次右）。因此走到第 $k$ 步时两人必然同在反对角线 $r + c = k + 2$ 上，列号可由行号与步数唯一确定：$c = k + 2 - r$。四维状态 $(r_1, c_1, r_2, c_2)$ 于是压缩成

其中 $k$ 是对角线号（起点 $k=2$），$k$ 维只需要滚动数组。

转移。 每人上一步只能来自"正上方"（行 $-1$）或"正左方"（行不变），共 4 种前驱组合，取 max 后加本步收益：

两人同在第 $k$ 条对角线上，$r_1 = r_2$ 当且仅当落在同一格，此时收益只加一份——这精确等价于题面"取走后的方格变为 0"。

小规模演示。 用真实数据 fgqs0（$N=3$，非零格 $(1,1){=}10,\ (1,3){=}5,\ (2,2){=}6,\ (2,3){=}4,\ (3,1){=}8,\ (3,2){=}2$）逐层写出 DP 表。行是 $k$（对角线号），列是状态 $(r_1, r_2)$，单元格是 $f[k][r_1][r_2]$：

读表要点：$k=2$ 只有起点、值 10（A 点的数只取一次）；$k=3$ 的 $(1,1)$ 表示两人都在 $(1,2)$（权 0），收益不加，值仍是 10；对比 $k=4$ 的两列——$(1,1)$ 表示两人都在 $(1,3)$，只加一份 5 得 15，而 $(1,2)$ 表示分别在 $(1,3)$ 与 $(2,2)$，加 $5+6=11$ 得 21，同格只计一份就体现在这里；每层可达状态随对角线变短而收缩，$k=6$ 只剩终点 $f=30$，即官方答案。

实现要点。 用 dict[(r1, r2)] 存当前层（天然跳过不可达状态），4 前驱用 cur.get((p1, p2), NEG) 取 max、NEG 哨兵挡掉不可达；lo, hi = max(1, k-n), min(n, k-1) 截断行号保证列不越界；r == 0 的行是输入结束标记。

代码

cur 是滚动的 $f[k-1]$，nxt 是 $f[k]$；gain 的三元表达式实现"同格只计一份"；内层生成器一次算出 4 个前驱的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int NEG = -1000000000;

int n;
int grid[22][22];
// cur[r1][r2]：两人同在斜线 k = 行+列 上、分别位于 (r1, k-r1)、(r2, k-r2) 时的最大和
int cur[22][22], nxt[22][22];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    while (true) {
        int r, c, v;
        cin >> r >> c >> v;
        if (r == 0 && c == 0 && v == 0) break;
        grid[r][c] = v;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cur[i][j] = NEG;
    cur[1][1] = grid[1][1];

    for (int k = 3; k <= 2 * n; k++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                nxt[i][j] = NEG;
        int lo = max(1, k - n), hi = min(n, k - 1);
        for (int r1 = lo; r1 <= hi; r1++) {
            int g1 = grid[r1][k - r1];
            for (int r2 = lo; r2 <= hi; r2++) {
                int gain = (r1 == r2) ? g1 : g1 + grid[r2][k - r2];
                int best = NEG;
                for (int p1 = r1 - 1; p1 <= r1; p1++)
                    for (int p2 = r2 - 1; p2 <= r2; p2++)
                        if (p1 >= 1 && p2 >= 1 && cur[p1][p2] > best)
                            best = cur[p1][p2];
                if (best > NEG) nxt[r1][r2] = best + gain;
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cur[i][j] = nxt[i][j];
    }
    cout << cur[n][n] << "\n";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:16
# update_at: 2026-10-04 13:17

import sys

NEG = -10**9  # 不可达状态哨兵（权值全为正，真实答案恒 >= 0）


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 1-indexed 方格，四周留 0 边界，未填数的格子自然为 0
    grid = [[0] * (n + 2) for _ in range(n + 2)]
    for r, c, v in zip(data, data, data):
        if r == 0:  # "0 0 0" 是输入结束标记
            break
        grid[r][c] = v

    # cur[(r1, r2)]：两人同在斜线 k = 行+列 上、分别位于 (r1, k-r1)、(r2, k-r2) 时
    # 已取得的最大和；同格被两人同时踩到时只计一次（取过的格子变 0）
    cur = {(1, 1): grid[1][1]}  # 两条路径都从 A 出发
    for k in range(3, 2 * n + 1):  # 下一条斜线（A 点所在斜线 k=2 已定）
        nxt = {}
        lo, hi = max(1, k - n), min(n, k - 1)  # 行号合法区间：列 = k-行 也在 1..n
        for r1 in range(lo, hi + 1):
            g1 = grid[r1][k - r1]
            for r2 in range(lo, hi + 1):
                # 两人不同格各取一份，同格只取一份
                gain = g1 if r1 == r2 else g1 + grid[r2][k - r2]
                # 上一步两人各自只能从"正上方(行-1)"或"正左方(行不变)"走来
                best = max(cur.get((p1, p2), NEG) for p1 in (r1 - 1, r1) for p2 in (r2 - 1, r2))
                if best > NEG:  # 至少有一个前驱可达
                    nxt[r1, r2] = best + gain
        cur = nxt

    print(cur[n, n])  # 终点 B 所在斜线上只剩 (n, n) 一个状态


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(N^3)$：$k$ 共 $2N-3$ 层，每层 $r_1, r_2$ 各 $O(N)$ 种，每状态 4 次字典查找。对照枚举路径对的约 $O(C(2N-2, N-1)^2)$（$N=9$ 时 $10^8$ 级）是决定性改进。
• 空间复杂度：$O(N^2)$：滚动保存两层状态，每层最多 $N^2$ 个 tuple 键。

总结

本题是"网格 DAG 上的双路径最大点权和"。核心两步：

1. 等步长消维——两条路径都恰走 $2(N-1)$ 步，第 $k$ 步必同在 $r+c=k+2$ 上，四维状态压成 $(k, r_1, r_2)$，并把 $k$ 做成滚动维，空间降到 $O(N^2)$。
2. 联合决策 + 同格合并——两条路径必须同时推进（先后贪心会互相抢格子），转移时用 $r_1 = r_2$ 判断同一格、收益只加一份，精确模拟"取过的格子变 0"。

两个易错点：起点和终点被两条路径共享，只应计一次（初值只写 $g[1][1]$，终点层 $r_1=r_2=N$ 自然只加一份）；不可达状态要靠哨兵挡在层外，否则 max 会把垃圾状态当合法前驱。

实测 verify.sh 3503：6/6 真实数据（含 $N=3,7,8,9,10$）输出全部一致，单点约 $0.016$ s、峰值内存约 $15$ MB，相对 $1000$ ms / $32$ MB 限制非常宽裕，Python 无超时风险。