题解：P7074 [CSP-J2020] 方格取数

· · 题解

P7074

对于这种路径问题我们不难想到一个套路即定义 dp_{i,j} 表示从 (1,1) 走到 (i,j) 的最大值，如果不能向上走，那么转移显然是这样的：

dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})+a_{i,j}

加上向上后，我们显然不能从左上直接向右下转移，怎么办呢？考虑再加一维。

直接改成 dp_{i,j,0/1/2} 表示从 (1,1) 到 (i,j) 上一步走右、下、上到达了 (i,j) 这个点。

考虑怎么转移 dp_{i,j,2}，由于是往上走，所以倒序转移是容易想到的，式子也很显然，只要上一步不是从上面走下来的都能转移。

dp_{i,j,2}=\max(dp_{i+1,j,0},dp_{i+1,j,2})+a_{i,j}

另外两个就正常转移就可以了，注意转移 dp_{i,j,1} 的时候不是从下面走上去的就行。

实现应该比定义从某一列走过来的更好写。

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pre(i, j, k) for(int i = j; i >= k; --i)
#define dout(i, x) cout << fixed << setprecision(i) << x << '\n'
#define PII pair<int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
#define inf 0x3fffffff

using namespace std;
const int N = 1e3 + 5;
int a[N][N], dp[N][N][4];
int n, m, ans = INT_MIN;

signed main() {
    FASTIO
    memset(dp, 0xcf, sizeof dp);
    cin >> n >> m;
    rep(i, 1, n)
        rep(j, 1, m) cin >> a[i][j];
    dp[0][1][0] = dp[1][0][0] = dp[0][1][1] = dp[1][0][1] = dp[0][1][2] = dp[1][0][2] = 0;
    rep(j, 1, m) {
        rep(i, 1, n) {
            dp[i][j][0] = max(dp[i][j - 1][2], max(dp[i][j - 1][0], dp[i][j - 1][1])) + a[i][j];
            dp[i][j][1] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i][j];
        }
        pre(i, n, 1) 
            dp[i][j][2] = max(dp[i + 1][j][0], dp[i + 1][j][2]) + a[i][j];
    }
    cout << max(dp[n][m][0], dp[n][m][1]);
    return 0;
}