几乎改得和题解一模一样了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
const ll INF = 1ll * -1e17;
int vis[1145][1419];
int a[1145][1419];
ll f[1145][1419][2];
int DFS(int x, int y, int q) {
if (x < 1 || x > n || y < 1 || y > m) return INF;
if (f[x][y][q] != INF) return f[x][y][q];
if (q == 0) {
f[x][y][q] = max(DFS(x + 1, y, 0), max(DFS(x, y - 1, 0), DFS(x, y - 1, 1))) + a[x][y];
} else {
f[x][y][q] = max(DFS(x - 1, y, 1), max(DFS(x, y - 1, 0), DFS(x, y - 1, 1))) + a[x][y];
}
return f[x][y][q];
}
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf ("%lld", &a[i][j]);
f[i][j][1] = f[i][j][0] = INF;
}
}
f[1][1][1] = f[1][1][0] = a[1][1];
printf ("%lld", DFS(n, m, 1));
// cout<<endl;
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j){
// cout<<f[i][j][1]<<' ';
// }cout<<endl;
// }cout<<endl;
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j){
// cout<<f[i][j][0]<<' ';
// }cout<<endl;
// }cout<<endl;
}
如果把 INF 改成 1e18 或 5e17 会 WA 0pts