♐ CSP_J 组真题
2020年
4. 方格取数

线上OJ:

洛谷:https://www.luogu.com.cn/problem/P7074 (opens in a new tab)
acwing:https://www.acwing.com/problem/content/2772/ (opens in a new tab)
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=2007 (opens in a new tab)

核心思想:

💡

设 f[i][j] 为以第 i 行第 j 列为终点的最大和。则可推断 f[i][j] 有三种来路:从上来,从左来,或者从下来。所以 f[i][j]取这三种来路的最大值 +a[i][j]
f[i][j][ → ] 记为 f[i][j][0] 表示从当前格子的 左边走到当前格子 能取到的最大整数之和。
f[i][j][ ↓ ] 记为 f[i][j][1] 表示从当前格子的 上边走到当前格子 能取到的最大整数之和。
f[i][j][ ↑ ] 记为 f[i][j][2] 表示从当前格子的 下边走到当前格子 能取到的最大整数之和。

列dp时要注意:

  1. 第 1 列只有从上来,所以第一列只有 f[i][1][1] 参与 dp方程, 即 f[i][1][1] = f[i-1][1][1] + a[i][1];

  2. 从第二列开始,为每个点罗列状态转移方程

    如果 [i][j] 是从左边 [i][j-1] 来的,则在左边点的三种可能性中挑最大值,+a[i][j]
        f[i][j][0] = max(f[i][j-1][0], f[i][j-1][1],f[i][j-1][2]) + a[i][j]
    如果 [i][j] 是从 [i-1][j] 上来,则在上边点的两种可能性中挑最大值,+a[i][j]
        f[i][j][1] = max(f[i-1][j][0], f[i-1][j][1]) + a[i][j]
    如果 [i][j] 是从 [i+1][j] 上来,则 [i+1][j] 绝不可能包含从 [i][j] 下来的可能性,否则就是回头路
    f[i][j][2] = max(f[i+1][j][0], f[i+1][j][2]) + a[i][j]    

另外,考虑到可能会溢出,本题中采用 long long

题解代码:

#include<bits/stdc++.h>
#define ll long long
#define inf -1e17
 
using namespace std;
 
ll f[1010][1010][3];
ll a[1010][1010];
int n, m;
 
ll maxx(ll a, ll b)
{
    return a>b ?a :b;
}
 
/*
每个点的 f[i][j]有三种来路:从上来,从左来,或者从下来。所以 f[i][j]取这三种来路的最大值 +a[i][j] 
f[i][j][ →] 记为 f[i][j][0]) 表示从当前格子的左边走到当前格子能取到的最大整数之和。
f[i][j][ ↓] 记为 f[i][j][1]) 表示从当前格子的上边走到当前格子能取到的最大整数之和。
f[i][j][ ↑] 记为 f[i][j][2]) 表示从当前格子的下边走到当前格子能取到的最大整数之和。
*/
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            f[i][j][0] = inf;	// 题目中求得是最大值,所以初始值都设为 负无穷大 
            f[i][j][1] = inf;
            f[i][j][2] = inf;
        }
    }
    // 初始化第一个点。因为f[1][1]是起始点,只能=a[1][1] 
    f[1][1][0]=a[1][1];
    f[1][1][1]=a[1][1];
    f[1][1][2]=a[1][1];
    // 初始化第一列。因为第一列只能是从上往下走,所以 f[i][1][1]只能 = f[i-1][1][1] + a[i][1]
    for(int i=2;i<=n;i++)
    {
        f[i][1][1] = f[i-1][1][1] + a[i][1];
    }
    // 从第二列开始,列状态转移方程 
	//  f[i][j][0] = max(f[i][j-1][0],f[i][j-1][1],f[i][j-1][2]) + a[i][j]
	//	f[i][j][1] = max(f[i-1][j][0],f[i-1][j][1]) + a[i][j]    如果[i][j]是从[i-1][j]下来,则 [i-1][j]绝不可能包含从[i][j]上来的可能性,否则就是回头路 
	//	f[i][j][2] = max(f[i+1][j][0],f[i+1][j][2]) + a[i][j]    如果[i][j]是从[i+1][j]上来,则 [i+1][j]绝不可能包含从[i][j]下来的可能性,否则就是回头路
    for(int j = 2; j <= m; j++)
    {
        for(int i = 1; i <= n; i++)	// 考虑 →和 ↓这两种情况。dp应该是从上往下 
        {
            f[i][j][0] = maxx(f[i][j-1][1], maxx(f[i][j-1][0], f[i][j-1][2])) + a[i][j];
            if(i >= 2) 
				f[i][j][1] = maxx(f[i-1][j][0],f[i-1][j][1])+a[i][j];  // ↓方向
        }
         
        for(int i = n-1; i >= 1; i--)  // 考虑 ↑情况。dp应该是从下往上 
        {
            f[i][j][2] = maxx(f[i+1][j][0], f[i+1][j][2]) + a[i][j];
        }
    }
    cout << maxx(f[n][m][0], maxx(f[n][m][1], f[n][m][2]));
    return 0;
}