20分求助
查看原帖
20分求助
483058
陈泽涵爱g编程楼主2021/9/21 11:51
#include<iostream>
#include<cstdio>
using namespace std; 
int map[10001][10001];
int v[10001][10001];
int dp[10001][10001];
int sx,sy,fx,fy;
int ans;
int dx[4]={1,0};
int dy[4]={0,1};
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&map[i][j]);
			dp[i][j]=map[i][j];
		}
	}
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
	for(int i=fx;i>0;i--){
		for(int j=1;j<=fy;j++){
			dp[i][j]+=max(dp[i-1][j],dp[i][j-1]);
			if(dp[i-1][j]>=dp[i][j-1]){
				v[i-1][j]=1;
			}else{
				v[i][j-1]=1;
			}
		}
	} 
	int ans=0;
	for(int i=sx;i>0;i--){
        for(int j=1;j<=sy;j++ ){
        	if(!v[i][j]&&(map[i-1][j]>0||map[i][j-1])){
				if(map[i-1][j]>=map[i][j-1]&&map[i-1][j]>0){
			    ans+=map[i-1][j]; 
				map[i-1][j]=0;
			     
			}else if(map[i-1][j]<map[i][j-1]&&map[i][j-1]>0){
				ans+=map[i][j-1];
				map[i][j-1]=0;
			}
			}else if(v[i][j]&&ans>0){
				dp[fx][fy]+=ans;
				if(map[i-1][j]>=map[i][j-1]){
				map[i-1][j]=0;
				if(map[i][j]<0){
					ans+=map[i][j];
					dp[fx][fy]-=map[i][j];
			}
			}else{
				map[i][j-1]=0;
			}
			}else if(v[i][j]&&ans<0){
				if(map[i][j]<0){
					ans+=map[i][j];
					dp[fx][fy]-=map[i][j];
				}
			}
		}		
	}
	cout<<dp[fx][fy];
	return 0;
}
                     
2021/9/21 11:51
加载中...