方格取数

形式化题目

给定 $n \times m$ 的方格图，第 $i$ 行第 $j$ 列的格子有权值 $a_{i,j}$ （可以为负）。从左上角 $(1,1)$ 出发、走到右下角 $(n,m)$ ，每一步只能向上、向下或向右走一格，不能走出边界，也不能重复经过已经走过的方格。求路径经过的所有格子的权值之和的最大值。

样例 1 中一条和为 9 的最优路径如下，加粗为路径经过的格子：

行\列	1	2	3	4
1	1		3	2
2	2	-1	4	-1
3				-1

路径为 $(1,1)\to(2,1)\to(2,2)\to(2,3)\to(1,3)\to(1,4)\to(2,4)\to(3,4)$ 。观察它的形状：第 1 列从第 1 行走到第 2 行；第 2 列只取第 2 行一格就向右；第 3 列从第 2 行向上走到第 1 行再向右；第 4 列从第 1 行一路走到第 3 行的终点。每一列都是"进一次、出一次"，列内走的总是一段连续的行区间——这不是巧合，而是本题最核心的结构。

正解

思路

关键观察：路径可以按列拆成连续段。

向右是唯一改变列号的走法，且只能让列号 $+1$ 、不能减小。从第 1 列到第 $m$ 列恰好需要 $m-1$ 次向右，因此列号序列为 $1,2,\dots,m$ 逐列推进：每一列恰好进入一次、离开一次，不存在跳列或回访（回访需要向左）。
进入一列后、离开它之前只能在列内竖直移动；不重访要求列内不能折返（折返必重复经过格子），所以列内访问的格子必然是入口行到出口行之间的一段连续区间，且走法唯一——在列内"怎么走"没有自由度，只有"从哪行进、从哪行出"两个参数。
第 $j$ 列的入口行等于第 $j-1$ 列的出口行（列间只能同行向右移动），第 1 列从第 1 行进入，第 $m$ 列的出口行必须是第 $n$ 行。

于是整条路径与"每列的出口行序列" $(c_1,c_2,\dots,c_m)$ 一一对应， $c_m = n$ ；给定出口行序列，按"各列走连续段、列间同行右移"拼出的路径一定合法（不同列格子互异、同列内单向扫过、右移恰好首次进入下一列）。状态因此只需一维：

dp(i) = \text{处理到当前列、从第 } i \text{ 行离开该列时的最大取数和。}

朴素做法。 直接枚举出口行序列是 $O(n^m)$ 的指数做法。改成 DP 后，设第 $j$ 列的前缀和为 $pre[i]$ （该列第 1 行到第 $i$ 行之和， $pre[0]=0$ ），常规转移是对每个出口行 $c$ 枚举入口行 $r$ ：

dp'(c) = \max_{1 \leqslant r \leqslant n} \bigl\{ dp(r) + \operatorname{seg}(r,c) \bigr\}, \qquad \operatorname{seg}(r,c) = \begin{cases} pre[c] - pre[r-1], & r \leqslant c \\ pre[r] - pre[c-1], & r \geqslant c \end{cases}

段和 $O(1)$ ，但内层还要枚举 $n$ 个 $r$ ，每列 $O(n^2)$ 、总复杂度 $O(n^2m)$ 。 $n=m=10^3$ 时是 $10^9$ ，跑不动。

优化：把两层枚举拆成两个单调扫描。 瓶颈在于每个 $c$ 都把全部 $r$ 重新比较一遍，而被加项可以按 $r$ 与 $c$ 的大小拆成两半、各自把与 $c$ 无关的部分提出来：

$r \leqslant c$ （入口在上方，向下走到 $c$ ）：

\max_{r \leqslant c} \bigl\{ dp(r) + pre[c] - pre[r-1] \bigr\} = pre[c] + \max_{r \leqslant c} \bigl\{ dp(r) - pre[r-1] \bigr\}

大括号与 $c$ 无关：自上而下扫描时维护运行最大值，一次就得到所有 $c$ 对应的候选。

$r \geqslant c$ （入口在下方，向上走到 $c$ ）：

\max_{r \geqslant c} \bigl\{ dp(r) + pre[r] - pre[c-1] \bigr\} = \max_{r \geqslant c} \bigl\{ dp(r) + pre[r] \bigr\} - pre[c-1]

同理自下而上维护后缀最大值。

两半恰好覆盖全部入口行（ $r=c$ 时两半同值，重复无害），对每个 $c$ 取两半较大者，就与暴力枚举 $r$ 的结果严格相等。每列从 $O(n^2)$ 降到 $O(n)$ ，总复杂度 $O(nm)$ 。

样例 1 逐列的 DP 值如下，行为出口行（1…3）、列为"离开第 $j$ 列"，每格是该状态下已收集的最大和：

离开列 $j$	行 1	行 2	行 3
1	1	3	1
2	1	2	4
3	9	8	5
4	11	10	9（答案）

第 1 行是第 1 列从第 1 行走到第 $i$ 行的段和（起点固定）；此后每格是"上一列的 max + 本列连续段"在两个方向上取大。例如 $dp_3(1) = 9$ 来自"列 2 结束在第 2 行（值 2）+ 列 3 从第 2 行向上走到第 1 行（ $4+3=7$ ）"。注意只有 $c_4 = 3$ 才是合法终点：第 4 列的 $dp_4(1) = 11$ 虽然更大，但路径没有到达 $(3,4)$ ，不能作答——答案必须取最后一列第 $n$ 行的状态，这正是易错点。

初值也要小心：权值可以为负，DP 里没有"空段"可选，每个状态都必须真实走满入口到出口的段，因此初始值就是第 1 列的真实段和（可以是负数），扫描用的哨兵只取一个远小于 $-10^{10}$ 的常量。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14/**
 * 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 ll NEG=-(ll)1000000000000000000LL;
vector<ll> advance_col(vector<ll>&dp, vector<ll>&pre){int n=dp.size(); vector<ll> lo(n),hi(n),res(n); ll best=NEG; for(int r=0;r<n;r++){best=max(best,dp[r]-pre[r]); lo[r]=best;} best=NEG; for(int r=n-1;r>=0;r--){best=max(best,dp[r]+pre[r+1]); hi[r]=best;} for(int c=0;c<n;c++) res[c]=max(pre[c+1]+lo[c], hi[c]-pre[c]); return res;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n,m; if(!(cin>>n>>m)) return 0; vector<vector<ll> > pre(m, vector<ll>(n+1)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ll v;cin>>v; pre[j][i+1]=pre[j][i]+v;} vector<ll> dp(n); for(int i=0;i<n;i++) dp[i]=pre[0][i+1]; for(int j=1;j<m;j++) dp=advance_col(dp,pre[j]); cout<<dp[n-1]<<'\n'; return 0;}

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#!/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 14:42
# update_at: 2026-10-02 14:42

import sys

NEG = -10**18  # max 扫描的初值：任何真实路径和都远大于它


def advance(dp: list[int], pre: list[int]) -> list[int]:
    """按列转移一列：由上一列每行的最优值 dp 推出本列每行的最优值。

    pre 是本列前缀和，pre[i] = 前 i 行之和（pre[0] = 0）。从进入行 r 走到离开行 c
    收集的格子是本列 [min(r,c), max(r,c)] 这一段，按 r <= c 与 r >= c 拆成两半，
    各用一次单调扫描取 max，不必两两枚举 (r, c)。
    """
    n = len(dp)
    lo: list[int] = []  # lo[c] = max_{r<=c} (dp[r] - pre[r])：进来的行在上方
    best = NEG
    for r, value in enumerate(dp):
        best = max(best, value - pre[r])
        lo.append(best)
    hi: list[int] = []  # hi[c] = max_{r>=c} (dp[r] + pre[r+1])：进来的行在下方
    best = NEG
    for r in range(n - 1, -1, -1):
        best = max(best, dp[r] + pre[r + 1])
        hi.append(best)
    hi.reverse()  # 倒着扫完再翻转，让下标对齐离开行 c
    return [max(pre[c + 1] + lo[c], hi[c] - pre[c]) for c in range(n)]


def solve() -> None:
    data = sys.stdin.buffer
    n, m = map(int, data.readline().split())

    # 按行读入、按列存前缀和：pre[j][i] = 第 j 列前 i 行之和
    pre = [[0] * (n + 1) for _ in range(m)]
    for i in range(n):
        row = list(map(int, data.readline().split()))
        for j, value in enumerate(row):
            pre[j][i + 1] = pre[j][i] + value

    dp = pre[0][1:]  # 第 1 列只能从第 1 行进入，走到第 r 行时已收集前 r 行
    for j in range(1, m):
        dp = advance(dp, pre[j])

    print(dp[-1])  # 终点固定在第 n 行、第 m 列


if __name__ == "__main__":
    solve()

advance() 即上面两个扫描：lo/hi 分别是自上而下、自下而上维护的运行最大值（hi 扫完 reverse() 以对齐出口行下标），最后一行推导式对每个出口行取两半较大者；solve() 只做读入（按行读、顺手累加列前缀和）、初始化与逐列调用。唯一要注意下标约定：正文公式按 1 基行号书写，代码是 0 基下标，公式里的 $pre[r-1]$ 、 $pre[c]$ 在代码中写作 pre[r]、pre[c+1]，含义完全一致。

复杂度

时间：读入与前缀和 $O(nm)$ ，逐列转移 $m-1$ 次、每次 $O(n)$ ，合计 $O(nm)$ ，与正解同阶。
空间：列前缀和表 $O(nm)$ ，DP 与扫描数组 $O(n)$ 。
$nm = 10^6$ 时实测 0.30s、峰值 53.9MB；答案量级可达 $10^{10}$ ，Python int 无溢出问题（换 C++ 需 long long）。

总结

单向（上/下/右）移动让列号单调推进，“不重访"让每列内的走法坍缩成一段连续区间——两个约束合起来，把看似指数的路径搜索压成了按列的一维 DP，状态就是"从哪行离开当前列”。
转移形如 $\max_r \{dp(r) + \text{段和}\}$ 且段和可按 $r$ 与 $c$ 的大小拆分时，把与 $c$ 无关的项提出后用前缀 max / 后缀 max 各扫一遍，即可把 $O(n^2)$ 的列内转移降到 $O(n)$ ；这是处理"两层枚举但被加项可分离"的通用套路。
易错点：终点必须取最后一列第 $n$ 行的状态（中间行可能有更大的假最优）；权值有负，初值与哨兵不能随手填 0。

目录

形式化题目

正解

思路

代码

复杂度

总结