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

· · 题解

题解：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 完笔。