瑞瑞 • 1天前
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; }
评论:
请先登录,才能进行评论