90分求调
查看原帖
90分求调
726291
ruanweijie楼主2023/10/14 22:12
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,a[1005][1005],f[1005][1005],down[1005][1005],up[1005][1005];
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++){
		f[i][1]=f[i-1][1]+a[i][1];
	}
	for(int j = 2;j<=m;j++){
		for(int i = 1;i<=n;i++){
			if(i==1){
				up[i][j]=f[i][j-1]+a[i][j];
			}
			else{
				up[i][j]=max(f[i][j-1],up[i-1][j])+a[i][j];
			}
		}
		for(int i = n;i>=1;i--){
		    if(i==n){
				down[i][j]=f[i][j-1]+a[i][j];
			}
			else{
				down[i][j]=max(f[i][j-1],down[i+1][j])+a[i][j];
			}
		}
		for(int i = 1;i<=n;i++){
			f[i][j]=max(f[i][j-1],max(down[i+1][j],up[i-1][j]))+a[i][j];
		} 
	}
	cout<<f[n][m];
}
2023/10/14 22:12
加载中...