20pts求调
查看原帖
20pts求调
735763
_ChongYun_楼主2023/10/6 16:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1111][1111][3];
int n,m,mp[1111][1111];
signed main(){
    cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=-0x3f;
		}
	}
	dp[1][1][0]=dp[1][1][1]=dp[1][1][2]=mp[1][1];
	for(int j=1;j<=m;j++){
	    for(int i=1;i<=n;i++){
	    	if(i==1&&j==1) continue;
	        dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][2])+mp[i][j];
	        dp[i][j][2]=max(dp[i][j-1][0],max(dp[i][j-1][1],dp[i][j-1][2]))+mp[i][j];
	    }
	    for(int i=n;i>=1;i--){
	    	dp[i][j][1]=max(dp[i+1][j][1],dp[i+1][j][2])+mp[i][j];
		}
	}
	cout<<max(dp[n][m][0],dp[n][m][2])<<endl;
	return 0;
}
2023/10/6 16:58
加载中...