P11086 [ROI 2019] 机器人高尔夫 (Day 2) 题解

· · 题解

简要题意

给出一个 n\times m 的矩形网格，上面有 k 个洞。A 和 B 两个人轮流推着一个球在网格上移动，每次可以使得球向右或者向下移动一步。当球被推出边界或者推到一个洞时游戏结束，如果被推出边界得分为 0，如果被推到一个洞里得分就是这个洞的权值。A 想使得分尽可能小，B 想使游戏得分尽可能大，A 先手，设 g(x,y) 为从 (x,y) 开始游戏最终获得的分数，求 \displaystyle \sum_{i=1}^n\sum_{j=1}^mg(i,j)。

暴力做法

我们考虑游戏进行的过程，很容易想到一个显然的 DP：

状态数量为 O(n\times m)，转移复杂度为 O(1)，总复杂度为 O(n\times m)。因为 n,m 都很大，所以这样的 DP 显然无法通过。可以发现状态数量很多，转移复杂度却很小，于是考虑优化 DP 的状态数量。

优化

考虑使用两种颜色给矩形网格进行染色，设 (i,j) 的颜色为 (i+j)\operatorname{and}1。此时我们发现同种颜色的格子只会由一个玩家来走，就可以不用 DP 数组的第三维了。

这样操作之后状态数没有改变，但是有助于进行进一步的转化。

此时假设当前的格子轮到 A 来走，而且当前格子的右边和下边都没有洞，那么 DP 的转移式可以这样转化：

dp_{i,j}\gets \min(\max(dp_{i+2,j},dp_{i+1,j+1}),\max(dp_{i+1,j+1},dp_{i,j+2}))

这可以等价为

dp_{i,j}\gets \max(dp_{i+1,j+1},\min(dp_{i,j+2},dp_{i,j+2}))

通过这个式子可以发现，一个位于 (i,j) 的洞只能对满足 dx\ge 0,dy\ge 0,dx+dy\le 2 且 i-dx\ge1,j-dy\ge1 的 (i-dx,j-dy) 这 O(1) 个点产生直接影响。而如果不受到某个洞的直接影响，dp_{i,j}\gets dp_{i+1,j+1}。

这是一个关键的观察，它启示我们用维护 f_{x-y} 代替维护 dp_{x,y} ，因为 dp_{i,j}\gets dp_{i+1,j+1}，而 i-j=(i+1)-(j+1)。

所以最终的做法是，我们预处理出那 k 个洞能直接影响到的范围，使用 std::vector 存储并且降序排序。枚举 A 是走颜色为 0 的点还是颜色为 1 的点，遍历 std::vector 里面被洞直接影响到的点，使用 std::map 来维护当前 x-y 对应的 f 以及上一次被更新前的位置 pos，每次转移之前统计答案，全部转移进行完之后再统计一遍答案，时间复杂度为 O(k\log k)，具体可以参见下面的核心代码：

int n, m, k;
ll res;
map<int, int> dp, pos;
map<pair<int, int>, int> val;
vector<pair<int, int> > v;
inline ll query(int x, int y) {
    if (!dp.count(x - y))return 0;
    return dp[x - y];
}
void calc(bool flag) {
    dp.clear(), pos.clear();
    for (auto [x, y] : v) {
        if (flag == (x + y & 1) && dp.count(x - y)) {
            (res += 1ll * dp[x - y] * (pos[x - y] - x)) %= mod;
        }
        if (val.count(make_pair(x, y))) {
            dp[x - y] = val[make_pair(x, y)];
        } else {
            dp[x - y] = flag == (x + y & 1) ?
                                min(query(x + 1, y), query(x, y + 1)) :
                                max(query(x + 1, y), query(x, y + 1));
        }
        pos[x - y] = x;
    }
    for (auto [i, j] : dp) {
        if (flag == (2 * pos[i] - i & 1)) {
            (res += 1ll * min(pos[i], pos[i] - i) * j) %= mod;
        }
    }
}

void solve() {
    fr(n, m, k);
    for (int i = 1; i <= k; i++) {
        int x, y, z;
        fr(x, y, z);
        v.emplace_back(x, y);
        val[make_pair(x, y)] = z;
        for (int dx = 0; dx <= 2; dx++) {
            for (int dy = 0; dx + dy <= 2; dy++) {
                if (x > dx && y > dy) {
                    v.emplace_back(x - dx, y - dy);
                }
            }
        }
    }
    sort(v.begin(), v.end(), greater());
    v.erase(unique(v.begin(), v.end()), v.end());
    calc(0);
    calc(1);
    fw((res + mod) % mod), pc('\n');
}