20分求调
查看原帖
20分求调
1407818
fby0506楼主2025/7/1 10:23
#include<bits/stdc++.h>
using namespace std;
const int N=1005; 
int a[N][N],dpUp[N][N],dpDown[N][N],dp[N][N];
int main() {
	memset(dpUp,0,sizeof(dpUp));
	memset(dpDown,0,sizeof(dpDown));
	memset(dp,0,sizeof(dp));
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>a[i][j];
	for(int j=1; j<=m; j++) {
		for(int i=1; i<=n; i++) {
			if(j==1 || j==m) {
				dp[i][j]=max(dp[i][j-1],dp[i-1][j])+a[i][j];
			}
			dpDown[i][j]=max(dp[i][j-1],dpDown[i-1][j])+a[i][j];
		}
		for(int i=n; i>=1; i--) {
			dpUp[i][j]=max(dp[i][j-1],dpUp[i+1][j])+a[i][j];
			dp[i][j]=max(dpUp[i][j],dpDown[i][j]);
		}
	}
	cout<<dp[n][m];
	return 0;
}
/*
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
*/
2025/7/1 10:23
加载中...