【前后缀DP+枚举】牛客小白月赛 D 遗迹探险

淩亂°似流年 2024-03-22 19:00 23阅读 0赞

[D-遗迹探险\_牛客小白月赛72 (nowcoder.com)][D-_72 _nowcoder.com]

题意：

![92bb7412412848cd9cf46e5e5314de82.png][]

![66d4073ef9514ddc9fdfca824c697058.png][]

思路：

因为传送门个数很少，且每个传送门只能使用一次，因此先预处理出(1,1)到(x,y)的最大收益，(x,y)到(n,m)的最大收益，然后暴力枚举使用的两个传送门即可

Code：

#include<iostream>
    #include<vector>
    #include<map>
    #include<queue>
    #include<algorithm>
    #include<math.h>
    using namespace std;
    #define pii pair<int,int>
    const int mxv=1e3+9;
    #define int long long
    const int inf=1e18;
    int n,m,T;
    int a[mxv][mxv];
    int dp1[mxv][mxv],dp2[mxv][mxv];
    pair<int,int> pa[9];
    void solve(){	
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++) cin>>a[i][j],dp1[i][j]=dp2[i][j]=-inf;
    	
    
    		
    	dp1[1][1]=a[1][1];
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			if(i+1<=n) dp1[i+1][j]=max(dp1[i][j]+a[i+1][j],dp1[i+1][j]);
    			if(j+1<=m) dp1[i][j+1]=max(dp1[i][j]+a[i][j+1],dp1[i][j+1]);
    		}
    	}
    	
    	dp2[n][m]=a[n][m];
    	for(int i=n;i>=1;i--){
    		for(int j=m;j>=1;j--){
    			if(i-1>=1) dp2[i-1][j]=max(dp2[i][j]+a[i-1][j],dp2[i-1][j]);
    			if(j-1>=1) dp2[i][j-1]=max(dp2[i][j]+a[i][j-1],dp2[i][j-1]);
    		}
    	}
    	cin>>T;
    	while(T--){
    		int k;
    		cin>>k;
    		for(int i=1;i<=k;i++) cin>>pa[i].first>>pa[i].second;
    		int ans=dp1[n][m];
    		for(int i=1;i<=k;i++){
    			int xx1=pa[i].first,yy1=pa[i].second;
    		
    			//int sum=dp1[xx1][yy1];
    			for(int j=i+1;j<=k;j++){
    				int xx2=pa[j].first,yy2=pa[j].second;
    				int sum=dp1[xx1][yy1]+dp2[xx2][yy2];
    				ans=max(sum,ans);
    
    				sum=dp1[xx2][yy2]+dp2[xx1][yy1];
    				ans=max(sum,ans);
    			}
    		}
    		cout<<ans<<"\n";
    	}
    	
    }
    signed main(){
    	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    	
    	int t;
    	//cin>>t;
    	t=1;
    	while(t--) solve();
    	return 0;
    }

[D-_72 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/56825/D
[92bb7412412848cd9cf46e5e5314de82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5e7a13cce1d343f0acbc4118262e2567.png
[66d4073ef9514ddc9fdfca824c697058.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/e82c6e6b385d4425be1d6fbe44dd8885.png