ac

瑞瑞  •  1天前


include<bits/stdc++.h>

using namespace std; long long dp1[1002][1002],dp2[1002][1002]; int a[1002][1002]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){
	cin>>a[i][j];
}

} memset(dp1,0xf0,sizeof dp1); memset(dp2,0xf0,sizeof dp2); dp1[1][0]=dp2[1][0]=0; for(int j=1;j<=m;j++){

for(int i=n;i>=1;i--){
	dp1[i][j]=max(dp1[i+1][j],max(dp1[i][j-1],dp2[i][j-1]))+a[i][j];
}
for(int i=1;i<=n;i++){
	dp2[i][j]=max(dp2[i-1][j],max(dp1[i][j-1],dp2[i][j-1]))+a[i][j];
}

} cout<<dp2[n][m]; return 0; }


评论:

请先登录,才能进行评论