题解 | #方格取数（number）#

此题非常好！！！

思路：基础取数 dp 的变式。

• 考虑只能向下走和向右走（很简单）
• 考虑只能向上走和向右走（很简单）
• 区别：既可以向上走又可以向下走
  • 所以我们考虑对于每一列，既进行向下的 dp 也进行向上的 dp （具体过程见代码）

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define mem2(p, x) memset(p, x, sizeof(p))

const int N = 1009;

int n, m, a[N][N];
ll dp[N][N], fu1[N], fu2[N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++)
            scanf("%d", a[i] + j);
    }
    memset(dp, 0x8f, sizeof(dp));
    mem2(fu1, 0x8f);
    mem2(fu2, 0x8f);
    dp[0][1] = 0;
    for(int i = 1; i <= n; i ++) dp[i][1] = a[i][1] + dp[i - 1][1];
    for(int j = 2; j <= m; j ++) {
        for(int i = 1; i <= n; i ++) {
            fu1[i] = max(fu1[i - 1], dp[i][j - 1]) + a[i][j];  /// 计算从上往下的答案
        }
        for(int i = n; i; i --) {
            fu2[i] = max(fu2[i + 1], dp[i][j - 1]) + a[i][j];  /// 计算从下往上的答案
        }
        for(int i = 1; i <= n; i ++)
            dp[i][j] = max(fu2[i], fu1[i]);  /// 综合得解
    }
    cout << dp[n][m];
    return 0;
}

本人造的一道魔改题（附链接：超级链接 ）