60pts求助(报以关注)
查看原帖
60pts求助(报以关注)
590925
_x_y_楼主2022/10/26 21:40
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
long long n, m, a[N][N];
long long f[N][N][2];
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> a[i][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			for(int k = 0; k <= 1; k++)
				f[i][j][k] = -1e18;
	f[1][1][0] = a[1][1];
	for(int i = 2; i <= n; i++)
		f[i][1][0] = f[i-1][1][0] + a[i][1];
	for(int j = 2; j <= m; j++){
		for(int i = 1; i <= n; i++)
			f[i][j][0] = max(f[i][j-1][0], max(f[i][j-1][1], f[i-1][j][0])) + a[i][j];
		for(int i = n; i >= 1; i--)
			f[i][j][1] = max(f[i][j-1][1], max(f[i][j-1][0], f[i+1][j][1])) + a[i][j];
	}
	cout << max(f[n][m][0], f[n][m][1]) << endl;
	return 0;
}
2022/10/26 21:40
加载中...