求批评指正
我的想法是 输入这个图之后 算一下从(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; }