方格取数

核心思路分析

移动特性的分析

题目规定小熊只能向上、向下或向右移动，且不能重复经过同一个方格。这一规则蕴含了两个关键特性：

• 列与列之间（单向推进）：由于不能向左移动，这意味着在第 $j$ 列移动时，只能跨入下一列（向右），而绝不可能从第 $j+1$ 列折返回第 $j$ 列。因此，动态规划的状态转移可以按列逐列递推。
• 同一列内部（方向唯一）：在同一列 $j$ 内，如果沿着垂直方向移动，为了不走回头路，只能始终向下或始终向上，绝不能出现“先下后上”或“先上后下”的情况。

因此，对于第 $j$ 列的任意方格 $(i, j)$，到达该格子的路径来源必然是以下三者之一：

1. 从左侧跨入：从第 $j-1$ 列的 $(i, j-1)$ 向右移动一步到达；
2. 从同列上方走下：从同列的 $(i-1, j)$ 向下移动一步到达；
3. 从同列下方走上：从同列的 $(i+1, j)$ 向上移动一步到达。

状态定义

基于上述移动特性，为了区分在同一列内的移动方向，我们需要将第 $j$ 列的 DP 状态拆分为自上而下和自下而上两种不同的走法：

设 $f[i][j][0]$ 表示到达方格 $(i, j)$ 且在第 $j$ 列的移动方向为向下（或刚从左侧跨入）时能获得的最大权值和。 设 $f[i][j][1]$ 表示到达方格 $(i, j)$ 且在第 $j$ 列的移动方向为向上（或刚从左侧跨入）时能获得的最大权值和。

状态转移方程

假设方格 $(i, j)$ 处的数值为 $a[i][j]$。

第一列特殊初始化

起点为 $(1, 1)$。由于第一列左侧没有格子，且只能从 $(1,1)$ 开始向下移动（无法向上移动），因此第一列的初始化逻辑如下：

• 起点：$f[1][1][0] = f[1][1][1] = a[1][1]$
• 向下的格子（$i \ge 2$）：$f[i][1][0] = f[i-1][1][0] + a[i][1]$
• 向上的格子（$i \ge 2$）：由于无法向上到达，赋值为非法状态 $-\infty$，即 $f[i][1][1] = -\infty$

后续列的递推（$j \ge 2$）

对于第 $j$ 列，我们需要分别进行两次单向扫描更新：

1. 自上而下更新（$i$ 从 $1$ 递增到 $n$）

   到达 $(i, j)$ 可以是从左侧 $(i, j-1)$ 跨过来（此时上一列无论是向上还是向下到达该点均可），或者是从同列上方 $(i-1, j)$ 走下来：

   $f[i][j][0] = \max\Big(\max(f[i][j-1][0], f[i][j-1][1]),\ f[i-1][j][0]\Big) + a[i][j]$

2. 自下而上更新（$i$ 从 $n$ 递减到 $1$）

   到达 $(i, j)$ 可以是从左侧 $(i, j-1)$ 跨过来，或者是从同列下方 $(i+1, j)$ 走上来：

   $f[i][j][1] = \max\Big(\max(f[i][j-1][0], f[i][j-1][1]),\ f[i+1][j][1]\Big) + a[i][j]$

目标状态与答案计算

目标终点为右下角 $(n, m)$。

到达 $(n, m)$ 时，既可能是从左侧 $(n, m-1)$ 跨入，也可能是沿着第 $m$ 列从上方走下来。因此最终答案为两种状态的极大值：

$\text{Ans} = \max(f[n][m][0], f[n][m][1])$

(注：由于小熊从 $(1,1)$ 出发且不能折返，在到达右下角 $(n, m)$ 时绝不可能处于自下而上的移动状态，因此 $f[n][m][1]$ 的值自然不会优于 $f[n][m][0]$，二者取 $\max$ 可以统一表述。)

正确性分析（如何保证不重复经过方格）

为了保证路径不重复经过任何方格，算法在结构上设立了三重约束：

1. 列级推进（无向左转移）

   状态按列单向递推（for j = 2 ... m），DP 转移方程中完全没有出现“从 $j+1$ 列转移到 $j$ 列”的可能。一旦离开第 $j-1$ 列，后续就再也不会回到该列。

2. 同列垂直方向隔离

   同一列内部，通过将 DP 状态拆分为 f[i][j][0]（向下）与 f[i][j][1]（向上）并采取不同的循环方向：

   • 更新向下状态 f[i][j][0] 时，采用 $i$ 从 $1 \to n$ 的正向循环，仅依赖上方的状态，保证这一步只会向下走；
   • 更新向上状态 f[i][j][1] 时，采用 $i$ 从 $n \to 1$ 的逆向循环，仅依赖下方的状态，保证这一步只会向上走。

   这杜绝了同列内“先下后上”或“先上后下”的迂回路径。

3. 跨列方向重置

   当在第 $j-1$ 列向下走完后，跨列进入第 $j$ 列，此时可以在第 $j$ 列选择向上走。因为第 $j$ 列是完全未曾踏入的新列，在第 $j$ 列向上走不会接触到第 $j-1$ 列已访问过的任何方格。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 使用极小值作为无效状态，注意数据范围防止相加溢出
const long long INF = 1e18;

int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

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

    // f[i][j][0]: 到达 (i, j) 且在第 j 列向下移动（或从左侧跨入）的最大权值和
    // f[i][j][1]: 到达 (i, j) 且在第 j 列向上移动（或从左侧跨入）的最大权值和
    vector<vector<vector<long long>>> f(n + 2, vector<vector<long long>>(m + 1, vector<long long>(2, -INF)));

    // 1. 初始化第一列（只能从 (1,1) 开始单向向下移动）
    f[1][1][0] = f[1][1][1] = a[1][1];
    for (int i = 2; i <= n; ++i) {
        f[i][1][0] = f[i - 1][1][0] + a[i][1];
        // f[i][1][1] 保持 -INF，因为第一列无法向上走
    }

    // 2. 按列递推（从第 2 列到第 m 列）
    for (int j = 2; j <= m; ++j) {
        // (1) 自上而下更新：i 从 1 到 n
        for (int i = 1; i <= n; ++i) {
            long long from_left = max(f[i][j - 1][0], f[i][j - 1][1]);
            f[i][j][0] = max(from_left, f[i - 1][j][0]) + a[i][j];
        }

        // (2) 自下而上更新：i 从 n 到 1
        for (int i = n; i >= 1; --i) {
            long long from_left = max(f[i][j - 1][0], f[i][j - 1][1]);
            f[i][j][1] = max(from_left, f[i + 1][j][1]) + a[i][j];
        }
    }

    // 3. 输出右下角 (n, m) 的最大权值和
    cout << max(f[n][m][0], f[n][m][1]) << "\n";

    return 0;
}

复杂度与细节提示

1. 数值范围与负数处理：由于方格中的数值可能为负数，数组未达到的非法状态必须初始化为负无穷（如 -1e18）。注意不能使用常规的 -1 或 -0x3f3f3f3f，以防累加负数后溢出。
2. 复杂度分析：
   • 时间复杂度：$O(n \times m)$。算法包含两层嵌套循环（外层 $m$ 列，内层两次 $n$ 的单向扫描），能在 $1.00\text{s}$ 内轻松通过 $n, m \le 1000$ 的全量测试数据。
   • 空间复杂度：$O(n \times m)$。若面对极致空间限制，可利用状态只与第 $j$ 列和第 $j-1$ 列相关的特性，使用滚动数组优化至 $O(n)$。