竞赛讨论区 > 求批评指正
头像
追~随~
发布于 2023-05-12 21:13
+ 关注

求批评指正

我的想法是 输入这个图之后 算一下从(1,1)点 到 任意一点 的最大值,存在f数组中, 再算一下 从任意一点 到 (n,m)的最大距离这样的话暴力枚举k个传送们,让他们会相传 ,枚举过程中 求 最大值 = f[第一个传送门][第一个传送门] + g[传到的门][传到的门]

然后再他们与 f[n][m]去最大值,为啥不对

#include <bits/stdc++.h>

using namespace std;

long long a[1001][1001];
long long t;
long long f[1010][1010];
long long g[1010][1010];
vector<pair<int,int>> b;

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(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    f[1][1]=a[1][1];
//    	cout<<1<<endl;
//	cout<<" 2222"<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
              f[i][j] = max(f[i-1][j]+a[i][j],f[i][j-1]+a[i][j]);  
//			printf("%d ",f[i][j]);
        }
//        cout<<endl;
    }
//	cout<<1<<endl;
	g[n][m]=a[n][m];
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			g[i][j] = max(g[i+1][j]+a[i][j],g[i][j+1]+a[i][j]);
//			cout<<g[i][j]<<" ";
		}
//		cout<<endl;
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)
//			cout<<g[i][j]<<" ";
//		cout<<endl;
//	}
	cin>>t;
	for(;t--;){
		b.clear();
		int k;
		cin>>k;
		for(int i=1;i<=k;i++){
			int x,y;
			cin>>x>>y;
			b.push_back(make_pair(x,y));
//			cout<<b[i].first<<" "<<b[i].second<<endl;
		}
		long long ans=f[n][m];
		for(int i=0;i<k;i++)
			for(int j=0;j<k;j++){
				if(i!=j){
					ans = max(ans,f[b[i].first][b[i].second]+g[b[j].first][b[j].second]);
				}
			}
		cout<<ans<<endl; 
	}
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐