思路与算法

因为不能向左，同一列内只能单方向走，否则必重复格子。第一列只能从上往下。处理后续列时，分别计算从上方往下走的up[i]=max(old[i],up[i-1])+a[i][j]，以及从下方往上走的down[i]=max(old[i],down[i+1])+a[i][j]。本列结束于i的最优值是两者最大。最后输出右下角。

正确性说明

进入一列后不可能返回左列；本列若同时出现上移与下移，就会在第一次转向时经过已走格子，因此合法本列段必单向。up、down分别穷尽这两类：从左直接进入当前行，或从相邻行延长本列单向段。只读上一列和同方向已算状态，不拼接两种方向，保证无重复。按列归纳得到终点最优。

复杂度

O(nm)时间、O(nm+n)空间，含矩阵与三条状态数组初始化；代码保存完整输入矩阵后按列访问。

易错点

这不是两次只向右下取数的NOIP2000同名题。值可能为负，不能把未到达状态初始化为可取0，答案也可能为负。累计和用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &row : a)
        for (int &x : row)
            cin >> x;
    vector<long long> old(n), up(n), down(n);
    old[0] = a[0][0];
    for (int i = 1; i < n; i++)
        old[i] = old[i - 1] + a[i][0];
    for (int j = 1; j < m; j++) {
        up[0] = old[0] + a[0][j];
        for (int i = 1; i < n; i++)
            up[i] = max(old[i], up[i - 1]) + a[i][j];
        down[n - 1] = old[n - 1] + a[n - 1][j];
        for (int i = n - 2; i >= 0; i--)
            down[i] = max(old[i], down[i + 1]) + a[i][j];
        for (int i = 0; i < n; i++)
            old[i] = max(up[i], down[i]);
    }
    cout << old[n - 1] << "\n";
}