P7311 [COCI2018-2019#2] Maja 题解

· · 题解

看到本题没有题解，那就由我来写一篇吧。

首先，看到这题，我想到了一种十分暴力的 dp 做法。

令 f_{i, j, k} 表示走了 k 步，最后到达 (i,j) 的最大数量。 状态转移较为简单，方程也不列了。不过，K\le10^9，很明显，这个算法是行不通的。

还好 n,m 的数据范围较小。因为 K 可以大于 n\cdot m，所以说，Maja 肯定要在几个点上来回走动，最后再回到终点。于是我们来考察一下这几个点的性质。

引理：Maja 一定是在一个点和与这个点相邻的权值最大的点周期性地来回地走动。

我们简单证明一下这个引理。假设 Maja 是在三个点上来回走动。这是不可能得到最优解的。因为此时，他不如选择其中权值最大的两个点进行走动，反而更优。

就比如说，这三个点分别是1,2,3，权值为a,b,c。如果这么来回走，那么就是1 \to 2 \to 3 \to 2 \to 1 \to 2 \to 3 \to 2 \cdots。

明显可以看出，周期为4，并且一个周期平均权值为 \dfrac{2b+a+c}{4}。

当然，我们还有两种决策，平均权值分别为 \dfrac{a+b}{2} 与 \dfrac{b+c}{2}。

因为 \dfrac{b+c}{2} + \dfrac{a+b}{2}=2 \cdot \dfrac{2b+a+c}{4}。

所以这两者平均权值必有一个大于后者。

综上，我们证明了必须在相邻两个点来回走动。

然后还是 dp。状态类似，就是步数上限变成了 n\cdot m。中途根据引理统计答案。

f_{i,j,k} = \max{f_{i-1,j,k-1},f_{i+1,j,k-1},f_{i,j-1,k-1},f_{i,j+1,k-1}} + a_{i, j}

其中 k 这一维用滚动数组可以优化掉。

计算过程中可以顺便统计一下答案，只要根据引理，取与当前这个点相邻的点中权值最大的即可。

时间复杂度 O(n^2m^2)，空间复杂度 O(nm)，足以通过此题。另外，很明显要开 long long。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[110][110], A, B;
typedef long long ll;
ll f[110][110][2], ans, K;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
bool valid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main() {
    scanf("%d%d%d%d%lld", &n, &m, &A, &B, &K);
    for (register int i = 1; i <= n; ++i)
        for (register int j = 1; j <= m; ++j) scanf("%d", a[i] + j);
    bool tag = 1;
    memset(f, 0xcf, sizeof f);
    f[A][B][1] = 0;
    for (register int k = 1; k <= min(1ll * n * m, K >> 1); ++k) {
        tag ^= 1;
        for (register int i = 1; i <= n; ++i)
            for (register int j = 1; j <= m; ++j) {
                ll maxc = 0;
                for (register int p = 0; p < 4; ++p) {
                    int nx = i + dx[p], ny = j + dy[p];
                    if (!valid(nx, ny)) continue;
                    f[i][j][tag] = max(f[i][j][tag], f[nx][ny][tag ^ 1] + a[i][j]);
                    maxc = max(maxc, 1ll * a[i][j] + a[nx][ny]);
                }
                ans = max(ans, (f[i][j][tag]) * 2 + (K / 2 - k) * maxc - a[i][j]);
            }
    } 
    printf("%lld", ans);
}