这是一份标准的 AC 代码。

解题核心思路

1. 动态规划 (DP)：由于不能重复经过走过的格子，且只能向右、上、下移动，这意味着一旦离开某一列向右移动，就无法再回到该列。因此，我们可以按列进行 DP。
2. 状态定义：f[i][j] 表示到达坐标 $(i, j)$ 的最大路径和。
3. 列内转移：对于第 $j$ 列的格子 $(i, j)$，路径可能来自：
   • 左侧：直接从 $(i, j-1)$ 向右走。
   • 上方：从 $(i-1, j)$ 向下走（前提是 $(i-1, j)$ 也是从左侧进入第 $j$ 列后一路向下走到的）。
   • 下方：从 $(i+1, j)$ 向上走（前提是 $(i+1, j)$ 也是从左侧进入第 $j$ 列后一路向上走到的）。
   • 注意：同一列内不能既向下走又向上走，否则会重复经过格子。
4. 两遍扫描：为了处理“既能从上面下来，又能从下面上来”的冲突，我们在处理每一列时，使用两个临时数组 up[] 和 down[]，分别计算“从上往下走”和“从下往上走”的最优值，最后取两者的最大值赋给 f[i][j]。

标准 C++ 代码

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

// 数据规模：n, m <= 1000
const int MAXN = 1005;
// 初始化负无穷大，注意要足够小，因为路径和可能是很大的负数
// 不能只用 -1 或 INT_MIN，建议用 -1e18
const long long INF = 1e18;

// f[i][j] 记录到达 (i, j) 的最大得分
long long f[MAXN][MAXN];
// 原图数据
int a[MAXN][MAXN];

// 临时数组，用于列内的 dp 计算
// up[i] 表示在当前列，只允许从左边过来或从上面下来到达 i 行的最大值
// down[i] 表示在当前列，只允许从左边过来或从下面上来到达 i 行的最大值
long long up[MAXN], down[MAXN];

int main() {
    // 1. 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    // 2. 读入数据并初始化 DP 数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            f[i][j] = -INF; // 先全部初始化为负无穷
        }
    }

    // 3. 处理第一列 (Base Case)
    // 第一列只能从 (1,1) 开始一直向下走，不能向上也不能从左边来
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) {
        f[i][1] = f[i - 1][1] + a[i][1];
    }

    // 4. 按列 DP (从第 2 列开始)
    for (int j = 2; j <= m; j++) {
        // --- 第一次扫描：计算 up 数组 (从上往下) ---
        // 对于第 i 行，只有两种选择：
        // 1. 从左边直接过来: f[i][j-1]
        // 2. 从上面一格走下来: up[i-1]
        
        // 第一行只能从左边来
        up[1] = f[1][j - 1] + a[1][j];
        for (int i = 2; i <= n; i++) {
            long long from_left = f[i][j - 1]; // 从左边来
            long long from_up = up[i - 1];     // 从上面来
            up[i] = max(from_left, from_up) + a[i][j];
        }

        // --- 第二次扫描：计算 down 数组 (从下往上) ---
        // 类似地，两种选择：
        // 1. 从左边直接过来: f[i][j-1]
        // 2. 从下面一格走上来: down[i+1]
        
        // 最后一行只能从左边来
        down[n] = f[n][j - 1] + a[n][j];
        for (int i = n - 1; i >= 1; i--) {
            long long from_left = f[i][j - 1]; // 从左边来
            long long from_down = down[i + 1]; // 从下面来
            down[i] = max(from_left, from_down) + a[i][j];
        }

        // --- 合并状态 ---
        // 这一格的最大值就是两种走法中的较大者
        for (int i = 1; i <= n; i++) {
            f[i][j] = max(up[i], down[i]);
        }
    }

    // 5. 输出终点 (n, m) 的最大得分
    cout << f[n][m] << endl;

    return 0;
}

易错点解析

1. 数据类型：题目中数值可能是负数，路径累加和可能超过 int 范围，也可能变成极小的负数。务必使用 long long，并且 INF 要设置得足够小（如 -1e18）。
2. 第一列处理：题目要求从左上角 $(1,1)$ 出发。在第一列中，小熊只能向下走，不能向上走（因为起点在最上面），也不能从左边过来（左边没格子）。这是一个特殊边界。
3. 上下扫描独立：在计算某一列时，不能直接在 f 数组上同时更新上下方向，必须拆分成 up 和 down 两个过程，最后合并。这是处理“无后效性”的关键技巧。

你好！我是你的 OI 教练。

这道题（CSP-J 2020 T4）是当年的压轴题，考察的是动态规划（DP）。

虽然题目是网格图，且可以“上下左右”走（除了向左），但只要抓住一个核心约束，这道题的思路就会变得非常清晰。

以下是解题思路提示：

1. 核心约束与方向分析

题目规定：不能重复经过已经走过的方格。 这意味着，当你从第 $j-1$ 列走到第 $j$ 列之后，你就再也回不去第 $j-1$ 列了。

• 宏观方向：路径整体是从左向右推进的。我们可以按列来进行 DP。

2. 列内的移动逻辑

在某一列 $j$ 内部，你既然不能走回头路，那么你在这一列的移动轨迹只有两种可能：

1. 从左边 $(k, j-1)$ 进这一列，然后一直向下走到 $(i, j)$。
2. 从左边 $(k, j-1)$ 进这一列，然后一直向上走到 $(i, j)$。 （当然也包括直接横着过来不移动的情况，这可以归入上面任意一种）。

绝对不可能出现“在这一列先向下走几步，再向上走几步”的情况，因为那样会重复经过格子。

3. DP 状态设计

基于上面的分析，对于第 $j$ 列的每一个格子 $(i, j)$，我们要计算两个临时值：

• up[i]：表示路径是从上往下（或者直接从左边）到达 $(i, j)$ 的最大得分。
  • 来源可能是：左边 $(i, j-1)$ 或者是 上边 $(i-1, j)$。
• down[i]：表示路径是从下往上（或者直接从左边）到达 $(i, j)$ 的最大得分。
  • 来源可能是：左边 $(i, j-1)$ 或者是 下边 $(i+1, j)$。

4. 算法流程

1. 数据类型：注意数字累加可能很大，也可能是负数，必须使用 long long，并且初始化为一个极小的负数（如 -1e18）。
2. 第一列特殊处理：起点在 $(1, 1)$，所以在第一列只能一直向下走。直接计算前缀和即可。
3. 从第 2 列开始遍历到第 $m$ 列：
   • 第一次扫描（从上往下）：计算 up 数组。
     • up[i] = max(dp[i][j-1], up[i-1]) + w[i][j]
     • 也就是比较“从左边过来”和“从上面下来”谁更大。
   • 第二次扫描（从下往上）：计算 down 数组。
     • down[i] = max(dp[i][j-1], down[i+1]) + w[i][j]
     • 也就是比较“从左边过来”和“从下面上来”谁更大。
   • 合并状态：dp[i][j] = max(up[i], down[i])。这一格的最大得分就是两种走法里的优胜者。

5. 代码实现细节

• 开一个二维数组 f[1005][1005] 存最终 DP 值。
• 在每一列计算时，可以用两个临时数组（或者变量）来辅助计算上下扫描的过程。
• 注意边界：第一行没有“上面”，最后一行没有“下面”。

试着按照这个“两遍扫描”的思路去写代码吧！这就是经典的 $O(nm)$ 线性 DP。