题目翻译
给定 $n\times m$ 的网格，每个格子里有一个正整数 $a_{i,j}$。你需要在从 $(sx,sy)$ 开始，执行 $k$ 次操作。每一操作可以选择不动或者走到任意一个四联通（上下左右）的格子。操作之后，可以获得所在格子的 $a_{i,j}$ 的收益。
$1\leq n,m\leq 50$
题目思路
可以证明，选择的路线一定是，移动若干步（可以是 $0$ 步）然后一直停留在一个格子获得收益。假设你选定了一条路径作为答案，那么你走到这条路径上的最大值后一直停留，一定是不比继续往后走差的。也不会出现在一个格子停一会儿转下一个更大的格子，因为这样不如把之前停留的步数留给后面更大的格子。
做法一：
考虑到停留在一个格子获得收益部分与你移动所花步数相关，因此，我们不妨枚举『行走步数』。设 $f_{i,x,y}$ 表示走了 $i$ 步停留在 $(x,y)$ 的收益最大路径所得到的收益。
转移枚举『行走步数』$i$，『起始点』$(x,y)$，『方向』，通过『起始点』和『方向』可以得到『目标点』$(tx,ty)$，转移即为 $f_{i+1,tx,ty}\gets \max f_{i,x,y}+a_{tx,ty}$。
但是，『行走步数』很大。可是稍微想一下就可以发现至多 $\mathcal O(n^2)$ 步就能到达。虽然说用 $\mathcal O(n)$ 步一定能从任意一点出发，到达网格任意一点。但是收益会有区别。例如下面这组数据：
6 3 1000000000
6 1
100 100 100
100 1 100
100 1 100
100 1 100
100 1 100
100 1 101虽然可以从 $(6,1)$ 两步到 $(6,3)$，但是经过 $1$ 收益太差了。我们必须要绕过 $1$ 走。
因此形如上方的网格，构造一个大数填充，小数做墙的网格，就可以强制走 $\mathcal O(n^2)$ 步。
因此状态是 $\mathcal O(n^4)$ 的，转移是 $\mathcal O(1)$ 的。
$n,m$ 同阶，时间复杂度 $\mathcal O(n^4)$。
做法二：
考虑枚举『最后停在哪一个格子』$(ex,ey)$。
那么你每次移动到 $(tx,ty)$ 的代价相较于待在 $(ex,ey)$，代价就是 $a_{ex,ey}-a_{tx,ty}$。
之后直接建图跑最短路。
负数边权可以直接忽略，因为你走到大的没有必要继续走下去，而显然这个更大的点之后会被枚举到。从而将图转化为非负权图，可以使用 Dijkstra 求解。
那么答案即为 $a_{ex,ey}\times k-dis((sx,sy),(ex,ey))$。也就是停在一直最后格子的收益减去赶路时间。
$n,m$ 同阶，时间复杂度 $\mathcal O(n^4\log n)$。
部分代码
这是我自己的代码。赛时看了一眼就会了，关键结论有点典，DP 部分也比较基础。
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
typedef long long ll;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
int n, m, k;
ll a[55][55];
int x, y;
ll dis[2520][55][55];
ll ans;
int main()
{
cin >> n >> m >> k >> x >> y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
ans = a[x][y] * k;
auto in = [&](int x, int y)
{ return 1 <= x && x <= n && 1 <= y && y <= m; };
memset(dis, 128, sizeof(dis));
dis[0][x][y] = 0;
for (int i = 1; i <= min(n * m, k); i++)
{
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= m; y++)
{
for (int _ = 0; _ < 4; _++)
{
int tx = x + dx[_];
int ty = y + dy[_];
if (!in(tx, ty))
continue;
chkmx(dis[i][tx][ty], dis[i - 1][x][y] + a[tx][ty]);
}
}
}
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++)
chkmx(ans, dis[i][x][y] + a[x][y] * (k - i));
}
cout << ans << endl;
return 0;
}滚动数组写法，空间复杂度更优，时间复杂度无差别。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int main() {
ll H, W, K;
cin >> H >> W >> K;
ll sx, sy;
cin >> sx >> sy;
sx--;sy--;
vector<vector<ll>> A(H, vector<ll>(W, 0));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) cin >> A[i][j];
}
vector<vector<ll>> from(H, vector<ll>(W, -2e18));
from[sx][sy] = 0;
for (int z = 0; z < 5000; z++) {
if (K == 0) break;
K--;
vector<vector<ll>> to = from;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (i > 0) to[i][j] = max(from[i-1][j], to[i][j]);
if (i < H-1) to[i][j] = max(from[i+1][j], to[i][j]);
if (j > 0) to[i][j] = max(from[i][j-1], to[i][j]);
if (j < W-1) to[i][j] = max(from[i][j+1], to[i][j]);
to[i][j] += A[i][j];
}
}
swap(from, to);
}
ll ans = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
ans = max(ans, from[i][j]+K*A[i][j]);
}
}
cout << ans << endl;
return 0;
}写的是第二种做法。
void dijkstra(ll s){
for(int i=0;i<v;i++){
d[i]=inf;
}
d[s]=0;
priority_queue<P,vector<P>,greater<P>> que;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
ll V=p.second;
if(d[V]<p.first) continue;
for(auto e:g[V]){
if(d[e.to]>d[V]+e.cost){
d[e.to]=d[V]+e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
int main(){
cincout();
ll n,m,v;
cin>>n>>m>>v;
ll p,q;
cin>>p>>q;
p--;
q--;
vector<vector<ll>> a(n,vector<ll>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) cin>>a[i][j];
}
ll ans=-inf;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
graph g(n*m);
vector<int> px={0,1,0,-1},py={1,0,-1,0};
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
for(int k=0;k<4;k++){
int nx=x+px[k],ny=y+py[k];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(a[nx][ny]>a[i][j]) continue;
g.add_edge(x*m+y,nx*m+ny,a[i][j]-a[nx][ny]);
}
}
}
g.dijkstra(p*m+q);
ll d=g.d[i*m+j];
chmax(ans,a[i][j]*v-d);
}
}
cout<<ans<<endl;
}