本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-12 15:33:11

题解：P7311 [COCI2018-2019#2] Maja

题意

给定 $n\times m$ 的网格和起点，每个格子的权值为 $c_{i,j}$，共可以走 $k$ 步，求最大的 $\sum_{i,j}^{走过网格i,j}c_{i,j}$。

其中，有 $n,m\le100,k\le10^9,2\mid k$。

思路

应为 $k$ 很大，所以一定会在某一些位置循环跑动，而循环节的长度为二时一定最优，下面给出证明：

设循环节长度为三且三个点的权值分别为 $a,b,c$，而此时的平均权值为 $\frac{a+2b+c}4$。
若循环节长度为二，会有两种方案，平均权值分别为 $\frac{a+b}2$ 和 $\frac{b+c}2$。
能够发现，$\frac{a+b}2+\frac{b+c}2=2\times \frac{a+2b+c}4$，所以前两者必有一个大于等于后者（当且仅当 $a=b=c$ 时等号成立）。

循环节大于三时证明与其类似，这里不再赘述。

那我们便可以把 $k$ 步转化为 $n\times m$ 步，在其范围内进行 DP，对于每一个网格取其相邻的权值最大网格为循环节，取得它们和的最大值即为答案。

时间复杂度 $O(n^2m^2)$，空间复杂度 $O(nm) $。

DP过程

设 $f_{k,i,j}$ 表示第 $k$ 步，网格坐标为 $(i,j)$ 时取得的最大值。

初始化 $f_{k,i,j}$ 为极大值，$f_{0,a,b}=0$。

转移：$f_{k,i,j}=\max{f_{k-1,i-1,j},f_{k-1,i+1,j},f_{k-1,i,j-1},f_{k-1,i,j+1}}+c_{i,j}$。

代码

#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define F(i,l,r) for(int i = l;i <= r;i++)
const int N = 1e6 + 50,M = 1e3 + 50;
const int INF = 0x3f3f3f3f3f3f3f3f,INT = 0x7fffffff;
const int mod = 1e9 + 7;

int n,m,stx,sty,q,ans=-INF;
int c[105][105],mx[105][105];
int f[3][105][105];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	memset(f,0xcf,sizeof f);
	cin>>n>>m>>stx>>sty>>q;
	F(i,1,n) F(j,1,m) cin>>c[i][j];
	F(i,1,n) F(j,1,m) mx[i][j]=max(max(c[i-1][j],c[i+1][j]),max(c[i][j-1],c[i][j+1]))+c[i][j];
	f[0][stx][sty]=0;
	for(int k=1;k<=min(q\/2,n*m);k++){
		int t=k&1,l=t^1;
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
			f[t][i][j]=max(max(f[l][i-1][j],f[l][i+1][j]),max(f[l][i][j-1],f[l][i][j+1]))+c[i][j];
			ans=max(ans,f[t][i][j]*2 + (q\/2-k)*mx[i][j] - c[i][j]);
		}
	}
	cout<<ans;

	return 0;
}

——$2024.10.14,11:28$ 完笔。

handezheng 的博客

博客