[COCI2018-2019#2] Maja
题目描述
蜜蜂 Maja 在一个神奇的牧场里为花朵传粉。牧场可用一个 \(N \times M\) 的矩阵表示。在第 \(i\) 行第 \(j\) 列有 \(C_{i,j}\) 朵未传粉的花。
Maja 从位于第 \(A\) 行第 \(B\) 列的蜂巢出发，并前往牧场的一些区域后返回。Maja 可以在 \(1\) 步内从当前区域前往相邻的区域（即位于原区域的左、右、上或下方的区域），但不会离开牧场。每当 Maja 经过一个区域，它将会将该区域所有未传粉的花全部进行传粉。但牧场是神奇的！Maja 在离开区域 \((i,j)\) 后，所有传过粉的花将全部消失，而紧接着将会有 \(C_{i,j}\) 朵未传粉的花重新生长。
由于 Maja 不能一直飞下去，因此它将在 \(K\) 步后感到劳累。Maja 在 \(K\) 步内从蜂巢出发并返回的途中，最多能为多少朵花传粉？
输入格式
第一行输入正整数 \(N,M,A,B,K\)。
接下来的 \(N\) 行，每行输入 \(M\) 个整数表示区域 \((i,j)\) 的花的数量 \(C_{i,j}\)。
蜂巢所在区域不会有任何花朵生长。
输出格式
输出 Maja 在 \(K\) 步内从蜂巢出发并返回的途中，被传粉的花的最大数量。
样例 #1
样例输入 #1
2 2 1 1 2
0 1
2 10
样例输出 #1
2
样例 #2
样例输入 #2
2 2 1 1 4
0 5
5 10
样例输出 #2
20
样例 #3
样例输入 #3
3 3 2 2 6
5 1 0
1 0 3
1 3 3
样例输出 #3
15
提示
样例 1 解释
Maja 从 \((1,1)\) 开始，先向下飞行，为 \(2\) 朵花传粉，然后再返回。
样例 2 解释
Maja 从 \((1,1)\) 开始，依次向右、下、上、左飞行。由于 Maja 经过了 \((1,2)\) 两次，因而它每经过一次，便可为 \(5\) 朵花传粉。
数据规模与约定
对于 \(40\%\) 的数据，\(K \le 10^4\)。
对于 \(100\%\) 的数据，\(2 \le N,M \le 100\)，\(1 \le A \le N\)，\(1 \le B \le M\)，\(2 \le K \le 10^9\)，\(0 \le C_{i,j} \le 10^9\)，\(K \bmod 2=0\)。
说明
本题分值按 COCI 原题设置，满分 \(110\)。
题目译自 COCI2018-2019 CONTEST #2 T4 Maja。
思路
首先对于本题我们需要看出三个很关键的要素：
-
最终一定是走过某些格子，然后原路返回到原点。
-
为了最大化价值，人物如果产生循环节，那么必然是走到循环节，然后兜上几圈再原路返回。
-
循环节大小为2。
对于 $ 3 $ 的证明：
假设 $ k $ 比较大 $ (k \geq n \times m) $ 必然是在某个环上绕圈，否则没地方走了。
然后，在某个长度大于2的环上绕圈必然不会比在该环相邻2个之和最大的两个点之间来回走更优。
我们把环上的相邻点两两分组，和最大的那组的平均值必然不小于总环的平均值。否则总和小于总和矛盾。
这些弄懂了之后我们就可以先设一个 DP 数组 $ f_{i,j,k} \(，\) f_{i,j,k} $ 表示走了 $ k $ 步之后达到点 $ (i , j) $ 的最大值。
由此我们可以推出状态转移方程：$ f_{i,j,k} = max({f_{i,j,k} , f_{i,j+1,k-1} , f_{i,j-1,k-1} , f_{i+1,j,k-1} . f_{i-1}{j}{k-1}}) $。
我们的大致思路完了可以自己去尝试写代码了，记得开longlong。
Code：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#define ll long long
#define prt printf
#define sc(ppt) scanf("%d" , &ppt)
#define scl(ppt) scanf("%lld" , &ppt)
using namespace std;
const ll IM = -9223372036854775807;
ll f[105][105][2] , w[105][105];
ll n , m , A , B , k , ans = IM;
ll Max(ll a , ll b , ll c , ll d){
return max({a , b , c , d});
}
signed main(){
scl(n) ; scl(m) ; scl(A) ; scl(B) ; scl(k) ; k >>= 1;
for(int i=0 ; i<=n+1 ; i++){
for(int j=0 ; j<=m+1 ; j++) w[i][j] = f[i][j][0] = f[i][j][1] = IM;
}
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=m ; j++) scl(w[i][j]);
}
f[A][B][0] = 0;
for(ll res=1 ; res<=min(k , n * m) ; res++){
ll now = res & 1 ; ll opt = now ^ 1;
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=m ; j++){
ll Temp = Max(f[i - 1][j][opt] , f[i + 1][j][opt] , f[i][j - 1][opt] , f[i][j + 1][opt]);
f[i][j][now] = max(Temp + w[i][j], IM * 1LL);
if(f[i][j][now] < 0) continue ;
ll dat = f[i][j][now] + Temp;
dat += (k - res) * (w[i][j] + Max(w[i - 1][j] , w[i + 1][j] , w[i][j - 1] , w[i][j + 1]));
ans = max(ans , dat);
}
}
}
prt("%lld" , ans);
return 0;
}