2020 方格取数 · 方案二按列动态规划

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 1943 字

三状态分别记从上方、下方、左方到达

2020
动态规划

正文

// CSP-J 2020 复赛 T4 · 方格取数（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2020D
//
// 方案二 · 按列动态规划
// 突破口在「只能向右、向上、向下」：这意味着一旦离开某一列就再也回不去，
// 而在同一列里，人只能沿着一个方向一直走（先向下就不会再向上，否则会撞回走过的格子）。
// 于是把「怎么到达 (i, j)」分成三种状态：
//   dp[i][j][0] 从上方来（在本列里一路向下走到 (i, j)）
//   dp[i][j][1] 从下方来（在本列里一路向上走到 (i, j)）
//   dp[i][j][2] 从左方来（刚从左边那一列跨过来）
// 转移也就清楚了：
//   向左跨过来：上一列三种状态取最大；
//   向下走：只能接「上一格也是向下来的」或「上一格是刚跨过来的」；
//   向上走：只能接「下一格也是向上来的」或「下一格是刚跨过来的」。
// 因为要先有「刚跨过来」的结果，每列的处理顺序固定为：先算 [2]，再正着算 [0]，再倒着算 [1]。
// 复杂度：O(n * m)，空间 O(n * m * 3)。

#include <bits/stdc++.h>
using namespace std;

const long long NEG = -(1LL << 60);
static long long dp[1005][1005][3];
static long long a[1005][1005];

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

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

    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = NEG;
        }
    }
    dp[1][1][0] = dp[1][1][1] = dp[1][1][2] = a[1][1];

    for (int j = 1; j <= m; j++) {
        if (j > 1) {
            for (int i = 1; i <= n; i++) {   // 从左边那一列跨过来
                long long best = max(dp[i][j - 1][0], max(dp[i][j - 1][1], dp[i][j - 1][2]));
                if (best != NEG) dp[i][j][2] = max(dp[i][j][2], best + a[i][j]);
            }
        }
        for (int i = 2; i <= n; i++) {       // 在本列里继续向下
            long long best = max(dp[i - 1][j][0], dp[i - 1][j][2]);
            if (best != NEG) dp[i][j][0] = max(dp[i][j][0], best + a[i][j]);
        }
        for (int i = n - 1; i >= 1; i--) {   // 在本列里继续向上，必须倒着枚举
            long long best = max(dp[i + 1][j][1], dp[i + 1][j][2]);
            if (best != NEG) dp[i][j][1] = max(dp[i][j][1], best + a[i][j]);
        }
    }

    cout << max(dp[n][m][0], max(dp[n][m][1], dp[n][m][2])) << "\n";
    return 0;
}

2020 方格取数 · 方案二 按列动态规划

正文

CSP-J 标程 · 复赛真题的其它内容

2020 方格取数 · 方案二按列动态规划