形式化题目

给定 $N \times N$ 的方格图，每格有一个非负整数 $a_{i,j}$（未在输入中出现的格子为 $0$）。 在图上取两条从 $A=(1,1)$ 到 $B=(N,N)$ 的路径，每条路每步只能向下或向右。

格子里的数只能被取走一次：某个格子被两条路先后经过时，只有第一次经过算数 （等价于"取走后变为 $0$"）。求两条路径取走的数字之和的最大值：

其中 $S(P)$ 是路径 $P$ 经过的格子集合。注意求和对象是并集，重合格子只计一次。

本题数据规模很小（$N \leqslant 10$），但路径对的组合数约 $2.4 \times 10^9$， 所以难点不在数据量，而在如何把两条路径的进度压缩进一个状态里。

样例（$N=8$）的输出为 67。下面用一个小例子说明"重合格只算一次"这个题眼。

样例讲解：取 $N=3$ 的网格，非零格为 $(1,1)=10$、$(1,3)=5$、$(2,2)=6$、$(2,3)=4$、 $(3,1)=8$、$(3,2)=2$。

两条最优路径分别是

• $P_1$：$(1,1) \to (1,2) \to (2,2) \to (2,3) \to (3,3)$，取到 $10, 6, 4$；
• $P_2$：$(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)$，取到 $8, 2$。

两条路只在起点 $(1,1)$ 重合：并集共取到 $10 + 6 + 4 + 8 + 2 = 30$，起点 $10$ 只算一次。 若按"两条路各自求和再相加"的直觉写法会得到 $20 + 20 = 40$，比正确答案还大——这是本题最容易踩的坑。

正解

思路

朴素做法是枚举所有路径对：

从 $(1,1)$ 到 $(N,N)$ 的路径条数是 $\binom{2N-2}{N-1}$，$N=10$ 时为 $48620$ 条，两两组合约 $2.4 \times 10^9$ 种，再乘上每次求和的 $O(N)$，显然不可行。

它失败的根源是把两条路径当成两个互相独立的对象。于是状态里要同时记录 “第一条走到哪、第二条走到哪”，也就是 $(i,j,k,l)$ 四个量——这个四维状态里一半以上是 "两条路步数不同步"的非法状态，纯属浪费。

关键观察：从 $(1,1)$ 到 $(N,N)$ 的任意一条合法路径，步数恒为 $2N-2$，且走完 $t$ 步后一定落在 反对角线 $i+j = t+1$ 上。（每步让 $i+j$ 恰好加 1，起点 $i+j=2$。）

所以可以让两条路齐步走：走完 $t$ 步时，两个终点必然在同一条反对角线上。只要记下两个终点的 行号 $i$ 和 $j$，列号就被 $t$ 唯一确定，两个位置是 $(i,\ t+1-i)$ 和 $(j,\ t+1-j)$。 状态由此从四维压成三维：

转移时，一条路到达 $(i,\ t+1-i)$，它的前一格只能是 $(i-1,\ t+1-i)$（从上方下来）或 $(i,\ t-i)$（从左边过来），对应上一层行号 $i-1$ 或 $i$。两条路各两种来源，共 4 种组合：

最后一项的指示函数 $[i \neq j]$ 就是去重：同一反对角线上行号相同蕴含列号相同 （$j = t+1-i$ 由 $i$ 唯一确定），此时两个终点是同一格，只能加一次。

初始状态 $f_1[1][1] = a_{1,1}$；$t=2$ 时两条路都还在 $(1,1)$，不产生新状态，所以循环从 $t=3$ 开始。

下表是上面 $N=3$ 例子中 $t=3$ 那一层的完整状态（反对角线 $i+j=4$，只列出可达格）： 第一列是行号对 $(i,j)$，中间一列给出对应的两个终点坐标，最后一列是该状态的最大收益。

例如 $f_3[2][3] = 24$ 的来源是 $f_2[1][2] = 10$（此时两路在 $(1,2)$ 与 $(2,1)$），加上 $(2,2)$ 的 $6$ 和 $(3,1)$ 的 $8$。而 $f_3[1][1]$ 只有 $15$：两条路都停在 $(1,3)$， 该格的值 $5$ 只加一次（$10 + 5 = 15$），不是 $10 + 5 + 5 = 20$。

继续推到 $t=4$ 得 $f_4[2][3] = f_4[3][2] = 30$，$t=5$ 收敛到 $f_5[3][3] = 30$，即样例的答案。

1
2
3
4
5t=1  state(1,1)  cells (1,1) / (1,1)   f=10   两条路都在起点，10 只算一次
t=2  state(1,2)  cells (1,2) / (2,1)   f=10   两条路在起点之后分道
t=3  state(2,3)  cells (2,2) / (3,1)   f=24   取到 6 与 8，两格不同，各自计入
t=4  state(2,3)  cells (2,3) / (3,2)   f=30   取到 4 与 2，两路分开到最远
t=5  state(3,3)  cells (3,3) / (3,3)   f=30   同时抵达 B，格子无值

状态里的 $i, j$ 是行号，格子坐标还要由列 $t+1-i$、$t+1-j$ 补出来，所以同一状态 (2,3) 在 $t=3$ 与 $t=4$ 对应的是不同的两对格子。可以看到两条路只在起点和终点汇合，中间两格始终不同， 全程没有任何重合格。

代码

Python 版：

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#!/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-09-30 03:03
# update_at: 2026-09-30 03:06

import sys


def read_grid(n: int, data: list[int]) -> list[list[int]]:
    """把三元组列表铺成 (n+2)×(n+2) 的网格，下标从 1 开始，界外补 0。

    以 `0 0 0` 结束；收尾行可能只给出一两个 0，用 zip 按位置切三元组即可自动丢弃余数。
    """
    grid = [[0] * (n + 2) for _ in range(n + 2)]
    triples = zip(*[iter(data)] * 3)  # 每 3 个相邻元素一组，余数自动丢弃
    for row, col, value in triples:
        if not (row or col or value):  # 0 0 0 是结束标记
            break
        grid[row][col] = value        # 重复给出的格子以后出现的数为准
    return grid


def best_two_paths(grid: list[list[int]], n: int) -> int:
    """两条 (1,1)→(n,n) 只向右/向下的路径能取得的最大数字和（同格只算一次）。

    两条路都走 s-1 步时，各自终点必在第 s 条反对角线 i+j=s 上，所以按步数同步推进：
    f[i][j] = 两条路分别停在 (i, s-i) 与 (j, s-j) 时的最大收益，s 为当前反对角线。
    这样状态从 O(n^4) 降到每层 O(n^2)、总和 O(n^3)，且天然保证两条路同步。
    """
    neg = -1  # 不可达状态用负数标记：本题所有数值非负，"有限"与"不可达"因此可区分
    f = [[neg] * (n + 1) for _ in range(n + 1)]
    f[1][1] = grid[1][1]  # 两条路都从 A 出发，起点数字只计一次

    for s in range(3, 2 * n + 1):  # 反对角线 i+j=2 上两条路都在 (1,1)，不必转移
        nf = [[neg] * (n + 1) for _ in range(n + 1)]
        rows = range(max(1, s - n), min(n, s - 1) + 1)  # 该反对角线上合法的行号
        for i, j in ((i, j) for i in rows for j in rows):
            # 两条路各自"上一步"只能从左边或上边来，共 4 种组合
            best = max(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1], f[i][j])
            if best >= 0:
                gain = grid[i][s - i] + (0 if i == j else grid[j][s - j])  # 同格只取一次
                nf[i][j] = max(nf[i][j], best + gain)
        f = nf

    return f[n][n]


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


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * 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-04 23:43
 * update_at: 2026-10-04 23:43
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 15;

int n;
int a[MAXN][MAXN]; // a[i][j] 表示格子 (i, j) 上的数字（未填的格子为 0）
int f[MAXN][MAXN]; // f[i][j]：两条路各走 s-1 步、终点行号为 i 和 j 时的最大收益（s 为当前反对角线）
int nf[MAXN][MAXN]; // nf 滚动保存下一层（反对角线 s+1）的 DP 表

// 读入网格：每行三个整数 行 列 值，"0 0 0" 结束。
void read_input() {
    cin >> n;
    while (true) {
        int r, c, v;
        cin >> r >> c >> v;
        if (r == 0 && c == 0 && v == 0) break;
        a[r][c] = v; // 重复给出的格子以后出现的数为准
    }
}

void solve() {
    // 初始：两条路都在起点 A(1,1)，起点数字只计一次
    // s=2 即反对角线 i+j=2，f[1][1] 表示两条路都停在 (1,1)
    memset(f, -1, sizeof(f)); // -1 表示不可达状态（本题数值非负，可用 -1 区分）
    f[1][1] = a[1][1];

    // 两条路同步推进：走完 s-1 步时终点必在反对角线 i+j=s 上，
    // 行号 i、j 定下后列号 s-i、s-j 唯一确定，状态从四维压成三维。
    for (int s = 3; s <= 2 * n; s++) {
        memset(nf, -1, sizeof(nf));
        // 该反对角线上合法的行号范围（列号 s-i 必须落在 1..n）
        int low = max(1, s - n);
        int high = min(n, s - 1);
        for (int i = low; i <= high; i++) {
            for (int j = low; j <= high; j++) {
                // 两条路各自的上一步只能从上方或左方来，共 4 种来源组合
                int best = max(max(f[i - 1][j - 1], f[i - 1][j]),
                               max(f[i][j - 1], f[i][j]));
                if (best < 0) continue; // 前一层无可达来源
                // 终点 1 在 (i, s-i)；终点 2 在 (j, s-j)
                int gain = a[i][s - i];
                if (i != j) gain += a[j][s - j]; // i==j 说明两路停在同一格，只取一次
                if (best + gain > nf[i][j]) nf[i][j] = best + gain;
            }
        }
        // 滚动：把这一层的结果作为下一层的"上一层"
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] = nf[i][j];
    }

    // 两条路同时到达 B(n,n)（反对角线 s=2n 上唯一状态）
    cout << f[n][n] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

• 时间：共 $2N-2$ 层，每层 $O(N^2)$ 个状态，每个状态 4 次比较的 $O(1)$ 转移，总计 $O(N^3)$。 $N \leqslant 10$ 时状态数不到 $10^3$。
• 空间：滚动保存相邻两层 $O(N^2)$ 的 DP 表，加上网格本身，总计 $O(N^2)$。

对照：未同步的四维写法 $f[i][j][k][l]$ 是 $O(N^4)$ 时间、$O(N^4)$ 空间。按反对角线同步推进 并没有改变算法本质，只是删掉了"两条路步数不一致"的非法状态，把维度压掉一维。

总结

原题的状态之所以看起来必须四维，是因为"两条路"的进度被当成两个独立变量。一旦注意到 所有合法路径的步数相同、第 $t$ 步必在第 $t+1$ 条反对角线上，两条路的进度就被绑在一起， 只需两个行号即可定位，状态降到三维，每个状态也只剩 4 种来源。

这类"同时进行多个同构过程、彼此有冲突（不能重复取同一格）"的题，都是同一个套路： 把多个过程按同一"时钟"同步推进，把各自的进度压进一个维度。做题时要特别留意舍去的那一项—— 这里的 $[i \neq j]$ 就是"重合格只算一次"的全部实现。

图示解析

这张图串起本题从题面到答案的主线：

1
2
3
4
5
6
7
8两条路径的最大取数和
`- 朴素：枚举路径对 -> C(2N-2,N-1)^2 ~ 2.4e9，不可行
   `- 瓶颈：两条路进度互相独立，状态被迫 (i,j,k,l) 四维
      `- 关键观察：任意合法路径步数恒为 2N-2，第 t 步在反对角线 i+j=t+1
         `- 同步推进：位置由行号 i 和步数 t 唯一确定 -> 状态 (t, i, j)
            `- 转移：4 种来源取最大，增量 = a[i][t+1-i] + (i!=j) * a[j][t+1-j]
               `- 去重：i==j 即同一格，只加一次（题眼）
                  `- 答案：f[2N-2][N][N]，复杂度 O(N^3) / O(N^2)

先看第一个节点：问题本身只是"取两条路"，没有别的操作。第二个节点说明朴素解为什么爆炸—— 不是路径多到没法枚举单条，而是路径对的组合数太大。第三个节点是本题唯一的建模决定： 把"两条路"换成"两条路齐步走"，用步数这个公共时钟绑住两条路的进度。 第四个节点给出状态定义与转移，其中最难记的是 $i=j$ 必须去重，否则会像样例里那样算出 40 而不是 30。 最后一个节点是答案位置与复杂度。