线上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 列只有从上来,所以第一列只有 f[i][1][1] 参与 dp方程, 即 f[i][1][1] = f[i-1][1][1] + a[i][1];
-
从第二列开始,为每个点罗列状态转移方程
如果 [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;
}