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

Qfaiser · 2024-12-24 19:48:28 · 题解

solution

方格取数，经典的动态规划问题，但有所不同。这里可以向上走，也要求不能重复取数。对于这个不同也很好处理，只需要多开一维记录当前格子从哪个方向转移，就可以避免类似刚从上面过来又往上走的问题。

所以，我们设 f_{i, j, k} 表示取数到 (i, j) 时的最大值，k=0 表示从左转过来的，k=1 表示从上转过来的，k=2 表示从下转过来的。

绿色是当前格子，绿色根据 k 是由黄色转移到的，黄色是由红色转移得到，下面是对应的三种情况。

for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
            f[i][j][0]=max({f[i][j-1][0], f[i][j-1][1], f[i][j-1][2]})+a[i][j];

for (int i=2; i<=n; i++)
      for (int j=1; j<=m; j++)
            f[i][j][1]=max(f[i-1][j][0], f[i-1][j][1])+a[i][j];

for (int i=n-1; i>=1; i--)
      for (int j=1; j<=m; j++)
            f[i][j][2]=max(f[i+1][j][0], f[i+1][j][2])+a[i][j];

因为有负数，所以实现的时候要注意初值设极小值。

code

#include <bits/stdc++.h>
using namespace std;
long long n, m, a[1005][1005], f[1005][1005][3];
int main () {
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            cin >> a[i][j];
    memset(f, -0x3f, sizeof f);
    f[1][1][0]=f[1][1][1]=f[1][1][2]=a[1][1];
    for (int j=1; j<=m; j++) {
        for (int i=1; i<=n; i++)
            f[i][j][0]=max({f[i][j-1][0], f[i][j-1][1], f[i][j-1][2]})+a[i][j];
        for (int i=2; i<=n; i++)
            f[i][j][1]=max(f[i-1][j][0], f[i-1][j][1])+a[i][j];
        for (int i=n-1; i>=1; i--)
            f[i][j][2]=max(f[i+1][j][0], f[i+1][j][2])+a[i][j];
    }
    cout << max({f[n][m][0], f[n][m][1], f[n][m][2]});
    return 0;
}