来源:CSP-J 2020 T4 (题面来源LUOGU
第一眼dfs，发现复杂度高的离谱3^(nm)。
第二眼打个最优化，设dp[x][y]为走到x,y是能取到最大值,如果当前搜索到的值小于dp[x][y]那么搜了也没用，剪枝。 大概30分?
第三眼发现只有三个方向考虑特定做法，这复杂度必须是O(nm）,考虑dp,dp[x][y]完全不够表示，如何知道dp[x][y]是从那里走过来的的呢，是从上面还是下面？
1.此时定义dp[x][y][fdir] 当fdir为0的时候表示肯定不从上面一格走到(x,y）,反之亦然。
2.不管fdir=0还是=1，都有可能从左边一格更新，即向右走.
3.这种情况肯定无效 我走下去再走上来，或者我走上去再走下来.
4.考虑左边一格的时候不知道是fdir=0大还是fdir=1大，因此仍需讨论
那么得出方程dp[x][y][0]=max(dp[x+1][y][0],dp[x][y-1][0],dp[x][y-1][1]);
dp[x][y][1]=max(dp[x-1][y][1],dp[x][y-1][0]，dp[x][y-1][1]);
为什么不需要讨论dp[x+1][y]或者dp[x-1][y]的fdir？ （见3
（我不知道怎么更新所以就写了一个超弱的dfs
#include <bits/stdc++.h> using namespace std; long long n, m, a[1000 + 10][1000 + 10]; long long dp[1000 + 10][1000 + 10][2]; // 0 = up , 1 = down , 2 =right const int uinf = -0x7ffffff; inline bool check(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } template <typename T> T m3x(T a, T b, T c) { return max(max(a, b), max(b, c)); } long long dfs(int x, int y, int fdir) { if (check(x, y) == 0) return uinf; if (dp[x][y][fdir] != uinf) return dp[x][y][fdir]; if (fdir == 0) { return dp[x][y][0] = m3x(dfs(x + 1, y, 0), dfs(x, y - 1, 1), dfs(x, y - 1, 0)) + a[x][y]; } else { return dp[x][y][1] = m3x(dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)) + a[x][y]; } } void in() { scanf("%lld%lld", &n, &m); for (int i = 1;i <= n;++i) { for (int j = 1;j <= m;++j) { scanf("%lld", &a[i][j]); dp[i][j][0] = dp[i][j][1] = uinf; } } } int main() { in(); dp[1][1][0] = dp[1][1][1] = a[1][1]; cout << dfs(n, m, 1); // 只需要fdir=1就行了，因为你不可能从终点下面一个走上来，那就越界了 }
还要开long long。
原文：https://www.cnblogs.com/Sikonihigh/p/14384536.html