题意: N*M(1<=N,M<=100)的方格图，每个方格值小于1e9，从起点x,y出发，K(小于1e9)步之内回到出发点，问最大的收获
思路：
首先我们假设最优的策略是找一条长度为 c 的路径到某一个点 ( xx , yy ) ，然后预留原路返回的步数 c ，将剩下的 k - 2c 步对着 ( xx , yy )和旁边的最大的一个格子进行反复横跳，可以获得最大值
那么处理的方法就是，创建记录到达 ( x , y ) 的最大收获数组 val[][] 以及相应所需要走的路径长度记录数组 sp[][] ，从起点开始BFS，对每一格的最大收获进行更新，一个格子的最大收获可以由四连块的方格的收获转移而来，将四联块的收获减去反复横跳获得的收获就能得到到达 ( xx , yy ) 的路径长度，然后去四联块中的最大值进行更新
时间复杂度大约是O(nm)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int d[4][2]={1,0,-1,0,0,1,0,-1}; 6 int n,m,sx,sy; 7 ll k,ans=0,res,ress; 8 ll g[110][110],sp[110][110],val[110][110]; 9 struct pt{ 10 int x,y,st; 11 ll val; 12 pt(int x,int y,int st,ll val):x(x),y(y),st(st),val(val){} 13 }; 14 15 int main(){ 16 cin>>n>>m>>sx>>sy>>k; 17 for(int i=1;i<=n;++i){ 18 for(int j=1;j<=m;++j){ 19 scanf("%lld",&g[i][j]); 20 } 21 } 22 queue<pt> q; 23 q.push(pt(sx,sy,0,0)); 24 memset(sp,0x3f,sizeof(sp)); 25 sp[sx][sy]=0; 26 val[sx][sy]=0; 27 while(!q.empty()){ 28 pt u=q.front(); 29 q.pop(); 30 ll tmp=0; 31 for(int k=0;k<4;++k) tmp=max(tmp,g[u.x+d[k][0]][u.y+d[k][1]]); 32 ll res=max(val[u.x][u.y]-(k-2*sp[u.x][u.y])/2*(tmp+g[u.x][u.y])+g[u.x][u.y],0ll); 33 for(int i=0;i<4;++i){ 34 int xx=u.x+d[i][0],yy=u.y+d[i][1]; 35 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&(xx!=sx||yy!=sy)){ 36 ll ttmp=0; 37 for(int k=0;k<4;++k) ttmp=max(ttmp,g[xx+d[k][0]][yy+d[k][1]]); 38 if(res+(k-2*sp[u.x][u.y]-2)/2*(ttmp+g[xx][yy])+g[xx][yy]>val[xx][yy]){ 39 val[xx][yy]=res+(k-2*sp[u.x][u.y]-2)/2*(ttmp+g[xx][yy])+g[xx][yy]; 40 sp[xx][yy]=sp[u.x][u.y]+1; 41 q.push(pt(xx,yy,sp[xx][yy],val[xx][yy])); 42 } 43 } 44 } 45 } 46 for(int i=1;i<=n;++i){ 47 for(int j=1;j<=m;++j){ 48 if(!g[i][j]||sp[i][j]>k/2) continue; 49 ans=max(ans,val[i][j]); 50 } 51 } 52 cout<<ans; 53 return 0; 54 }