[CSP-J 2020] 方格取数

题意

给出一个 n × m 的整数方格。

从左上角 (1,1) 出发，到右下角 (n,m) 结束。每一步只能向上、向下或向右走，不能出界，也不能重复经过同一个格子。

要求经过格子的数字和最大。

思路

先看最直接的暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据 DFS 枚举所有合法路径，用来帮助理解题意和对拍。

const int MAXN = 8;
const long long NEG_INF = -(1LL << 60);

int n, m;
int a[MAXN][MAXN];
bool vis[MAXN][MAXN];
long long ans = NEG_INF;

int dx[3] = {-1, 1, 0};
int dy[3] = {0, 0, 1};

void dfs(int x, int y, long long sum) {
    if (x == n && y == m) {
        ans = max(ans, sum);
        return;
    }

    for (int k = 0; k < 3; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx < 1 || nx > n || ny < 1 || ny > m) {
            continue;
        }
        if (vis[nx][ny]) {
            continue;
        }

        vis[nx][ny] = true;
        dfs(nx, ny, sum + a[nx][ny]);
        vis[nx][ny] = false;
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    vis[1][1] = true;
    dfs(1, 1, a[1][1]);

    cout << ans << '\n';
    return 0;
}

下面是另一种「路径搜索」风格的暴力写法。它把"下一步往上、往下、往右走"看成递归树上的分支，并用 used 防止重复经过格子：

另一种暴力写法：路径搜索

cpp

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// brute_01_style.cpp：路径搜索风格暴力，每一层递归决定下一步往哪个方向走。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 8;
const long long NEG_INF = -(1LL << 60);

int n, m;
int a[MAXN][MAXN];
bool used[MAXN][MAXN];
long long answer = NEG_INF;

int dx[3] = {-1, 1, 0};
int dy[3] = {0, 0, 1};

void dfs(int dep, int x, int y, long long sum) {
    if (x == n && y == m) {
        answer = max(answer, sum);
        return;
    }

    // dep 表示已经走了多少步。每一层从 3 个方向中选择一个继续走。
    for (int choice = 0; choice < 3; choice++) {
        int nx = x + dx[choice];
        int ny = y + dy[choice];

        if (nx < 1 || nx > n || ny < 1 || ny > m) {
            continue;
        }
        if (used[nx][ny]) {
            continue;
        }

        used[nx][ny] = true;
        dfs(dep + 1, nx, ny, sum + a[nx][ny]);
        used[nx][ny] = false;
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    used[1][1] = true;
    dfs(0, 1, 1, a[1][1]);

    cout << answer << '\n';
    return 0;
}

brute.cpp 用 DFS 枚举当前位置往上、往下、往右的所有合法走法，并用 vis 防止重复经过格子。
这个做法很贴近题意，但路径数太多，只适合小数据对拍。

关键观察是：因为不能向左，所以路径一定按列从左往右推进。

进一步想，在同一列里如果你：

先向上走一段，再向下走
或先向下走一段，再向上走

那一定会回到这一列里已经走过的格子，和题意矛盾。

所以在同一列内部，方向只能保持单调——要么一直向上，要么一直向下。

二维 DP 状态

设 $f_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$ 能获得的最大和。目标就是 $f_{n,m}$ 。

因为不能向左走，我们按列从左往右递推。对于第 $j$ 列，你只能从第 $j-1$ 列的某一行 $k$ 进入当前列，然后在当前列内单调地走到第 $i$ 行。

如果要写转移式，直观上是这样（不优化）：

f_{i,j} = a_{i,j} + \max_{1 \le k \le n} \begin{cases} f_{k,\,j-1} + \sum_{t=k}^{i} a_{t,j}, & k \le i \;\text{（从上往下走）} \\[6pt] f_{k,\,j-1} + \sum_{t=i}^{k} a_{t,j}, & k \ge i \;\text{（从下往上走）} \end{cases}

这个转移是 $O(n^2)$ 每列，总 $O(n^2 m)$ ，太大了，必须优化。

观察：上面的 $\max$ 其实是两个独立方向的问题。

从上往下走：如果你停在 $i-1$ 行，再往下走一步就是 $i$ 行，所以 $f_{i-1,j}$ 的值已经包含了前面最优的累计。
从下往上走：对称推理。

因此可以拆成两次 $O(n)$ 扫描：

优化：一次 down 扫描 + 一次 up 扫描

记 $dp_i$ 为上一列（第 $j-1$ 列）结束在第 $i$ 行的最大和，即 $dp_i = f_{i,\,j-1}$ 。

处理第 $j$ 列时，用两个临时数组 down 和 up：

down[i]：在第 $j$ 列内最后是"从上往下"走到第 $i$ 行的最优值
up[i]：在第 $j$ 列内最后是"从下往上"走到第 $i$ 行的最优值

转移式：

$down_i = \max(dp_i,\ down_{i-1}) + a_{i,j}$
$up_i = \max(dp_i,\ up_{i+1}) + a_{i,j}$

含义：down[i] 要么从左边直接跨到第 $i$ 行（ $dp_i$ ），要么从同列上方走下来（ $down_{i-1}$ ），取更大的再加上当前格。up[i] 对称。

扫完之后合并：

$dp_i = \max(down_i,\ up_i)$ —— 这就是新一列的 $f_{i,j}$ 。

每列只做两趟 $O(n)$ 扫描，总复杂度 $O(nm)$ 。

因为 $dp_i$ 每列滚动更新，代码里只需要一维数组，空间 $O(n)$ 。 但理解时始终可以把它看成 f[i][j] 的列递推——二维状态，逐列推进。

样例 1 DP 表格

以样例 1 为例： $n = 3, m = 4$ ，方格为：

text

1
2
3 1 -1  3  2
 2 -1  4 -1
-2  2 -3 -1

逐列计算 $down_i$ 、 $up_i$ 和更新后的 $dp_i$ （初始 $dp = [0, -\infty, -\infty]$ ）：

列 $j$	行 $i$	$a_{i,j}$	$down_i$	$up_i$	$dp_i = \max(down_i, up_i)$
1	1	1	$\max(0, -\infty)+1 = 1$	$\max(0, -\infty)+1 = 1$	1
1	2	2	$\max(-\infty, 1)+2 = 3$	$\max(-\infty, -\infty)+2 = -\infty$	3
1	3	-2	$\max(-\infty, 3)+(-2) = 1$	$\max(-\infty, -\infty)+(-2) = -\infty$	1
2	1	-1	$\max(1, -\infty)+(-1) = 0$	$\max(1, 2)+(-1) = 1$	1
2	2	-1	$\max(3, 0)+(-1) = 2$	$\max(3, 3)+(-1) = 2$	2
2	3	2	$\max(1, 2)+2 = 4$	$\max(1, -\infty)+2 = 3$	4
3	1	3	$\max(1, -\infty)+3 = 4$	$\max(1, 6)+3 = 9$	9
3	2	4	$\max(2, 4)+4 = 8$	$\max(2, 1)+4 = 6$	8
3	3	-3	$\max(4, 8)+(-3) = 5$	$\max(4, -\infty)+(-3) = 1$	5
4	1	2	$\max(9, -\infty)+2 = 11$	$\max(9, 7)+2 = 11$	11
4	2	-1	$\max(8, 11)+(-1) = 10$	$\max(8, 4)+(-1) = 7$	10
4	3	-1	$\max(5, 10)+(-1) = 9$	$\max(5, -\infty)+(-1) = 4$	9

答案 $dp_3 = 9$ ，与样例输出一致。最优路径经过的格子为 $(1,1) \to (2,1) \to (2,2) \to (2,3) \to (1,3) \to (1,4) \to (2,4) \to (3,4)$ ，和为 $1+2+(-1)+4+3+2+(-1)+(-1) = 9$ 。

代码

cpp

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/**
 * 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: 2025-11-28 15:41
 * update_at: 2025-11-28 15:41
 */
/*
 * 题目：[CSP-J 2020] 方格取数 (luogu 7074)
 * 核心思路：
 * 1. 不能向左，按列从左往右 DP，定义 f[i][j] = 走到 (i,j) 的最大和。
 * 2. 同一列内方向只能单调，否则会重复走格子。
 * 3. 每列做两次 O(n) 扫描：
 *    - down[i]：从上往下走到第 i 行的最优值
 *    - up[i]：从下往上走到第 i 行的最优值
 * 4. 取两者较大值存入 f[i][j]。
 */

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

// ===== 输入数据 =====
const int MAXN = 1005;
int n, m;
int a[MAXN][MAXN];

// ===== DP 数组 =====
long long f[MAXN][MAXN];    // f[i][j] = 走到 (i,j) 的最大和
long long down[MAXN][MAXN]; // down[i][j] = 第 j 列从上往下到 i 行的最优值
long long up[MAXN][MAXN];   // up[i][j] = 第 j 列从下往上到 i 行的最优值

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    // 第一列：从 (1,1) 出发只能往下走
    down[1][1] = a[1][1];
    up[1][1] = a[1][1];
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) {
        down[i][1] = down[i - 1][1] + a[i][1];
        up[i][1] = down[i][1]; // 第一列没有向上走的机会
        f[i][1] = down[i][1];
    }

    // 第 2 列到第 m 列
    for (int j = 2; j <= m; j++) {
        // 从上往下扫描
        down[1][j] = f[1][j - 1] + a[1][j];
        for (int i = 2; i <= n; i++)
            down[i][j] = max(f[i][j - 1], down[i - 1][j]) + a[i][j];

        // 从下往上扫描
        up[n][j] = f[n][j - 1] + a[n][j];
        for (int i = n - 1; i >= 1; i--)
            up[i][j] = max(f[i][j - 1], up[i + 1][j]) + a[i][j];

        // 合并
        for (int i = 1; i <= n; i++)
            f[i][j] = max(down[i][j], up[i][j]);
    }

    cout << f[n][m] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(n)$

总结

这题最重要的不是直接想完整路径，而是先抓住“列内方向不能来回变”的性质。

一旦看出每一列只会单调上走或单调下走，整题就可以压成按列的两遍扫描 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。