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