90pts 求助
查看原帖
90pts 求助
322620
Nygglatho楼主2022/10/15 17:02

几乎改得和题解一模一样了

#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 改成 1e185e17 会 WA 0pts

2022/10/15 17:02
加载中...