1.题目大意
给定一个 \(n*m\) 的矩阵，矩阵中每个点 \((i,j)\) 都有一个权值 \(f_{(i,j)}\)。每次可以向上，向下或向右走。问从 \((1,1)\) 走到 \((n,m)\)，经过的路径上点的权值之和最大是多少？
2.思路
这道题我们不难想到动态规划。但是与一般的动规不同的是，本题中有上下右三种走法，因此不能用一般的 \(dp\) 解决。
因此我们可以采用化繁为简的策略，即将三种走法分解成 向上、向右 和 向下、向右 两种方法，分别存在数组 \(dp1[]\) 和 \(dp2[]\) 中。
即用 \(dp1_{(i,j)}\) 表示从 \(i\) 到 \(j\) 只用向下和向右两种走法能凑出的最大值，用 \(dp2_{(i,j)}\) 表示从 \(i\) 到 \(j\) 只用向上和向右两种走法能凑出的最大值。
然后本题还有一个易错点就是，因为可以向上和向下但又要保持不能走重复点，所以应该一列一列从左往右推，也可以理解为将矩阵 \(90\) 度翻转一下，然后一行一行从上往下推。
对于第二列开始的每一个点，我们先将其 \(dp\) 值赋值为 由它前一列的同一行向右走一格所得到的价值，即
\[dp1_{(i,j)} = dp2_{(i,j)} = max (dp1_{(i,j-1)}, dp2_{(i,j-1)}) + a_{(i,j)}; \]然后我们再分别考虑向上或向下走得到的价值，并与之前得到的初始值取较大值：
\[dp1_{(i,j)} = max (dp1_{(i,j)}, dp1_{(i-1,j)} + a_{(i,j)}); \]\[dp2_{(i,j)} = max (dp2_{(i,j)}, dp2_{(i+1,j)} + a_{(i,j)}); \]最后，问题的答案就是两种走法得到权值的最大值。
3.注意事项
-
1.因为我们是从第二列开始跑 \(dp\)，所以要先初始化第一列，第一列的 \(dp\) 值就是其对应点的权值；
-
2.因为 \(dp\) 数组需要取最大值，所以要先将其初始值赋为一个很小的值；
-
3.因为图中最多会有 \(10^6\) 个点，且每个点权值最大为 \(10^4\)，也就是说答案的最大值为 \(10^10\)。因此我们需要开 \(long\) \(long\)；
-
4.在统计往上走的 \(dp\) 值时，因为是从下往上更新，所以要使用倒序循环枚举。
4.代码
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
//不开long long见祖宗！！！
using namespace std;
#define N 1010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(),cin.tie(),cout.tie()
int n, m, a[N][N], dp_up[N][N], dp_down[N][N];
void init () {
For (i, 1, n) {
For (j, 1, n) {
dp_up[i][j] = dp_down[i][j] = -1e18;
}
} //将全图初始值赋为一个很小的值
dp_up[1][1] = a[1][1];
dp_down[1][1] = a[1][1]; //将出发点 dp 值赋为 a[1][1]
return ;
}
signed main() {
IOS;
cin >> n >> m;
For (i, 1, n) {
For (j, 1, m) {
cin >> a[i][j];
}
}
init (); //初始化 dp 数组
For (i, 2, n) {
dp_up[i][1] = dp_up[i - 1][1] + a[i][1];
dp_down[i][1] = dp_down[i - 1][1] + a[i][1];
} //初始化第一列，其值为其上面的数的 dp 值加上这个点的权值。
For (j, 2, m) {
For (i, 1, n) {
int t = max (dp_up[i][j - 1], dp_down[i][j - 1]);
dp_up[i][j] = dp_down[i][j] = t + a[i][j];
} //将其先赋值为上一列同一行的数往右走一步得到的价值
For (i, 2, n) {
int t = dp_up[i - 1][j] + a[i][j];
dp_up[i][j] = max (dp_up[i][j], t);
} //模拟向下走得到的价值，将其与向右走得到的价值取 max
for (int i = n - 1; i >= 1; i --) {//因为往上走要先更新下面点的 dp 值，所以需要倒序循环。
int t = dp_down[i + 1][j] + a[i][j];
dp_down[i][j] = max (dp_down[i][j], t);
} //模拟向上走得到的价值，将其与向右走得到的价值取 max
}
//答案为方案1的最大价值与方案2的最大价值中的较大值
cout << max (dp_up[n][m], dp_down[n][m]) << endl;
return 0;
}