LCP 57-打地鼠

欢迎各位勇者来到力扣城，本次试炼主题为「打地鼠」。
![middle_img_v2_d5d09656-0616-4a80-845e-ece461c5ba9g.png](https://pic.leetcode-
cn.com/1650273183-nZIijm-
middle_img_v2_d5d09656-0616-4a80-845e-ece461c5ba9g.png){:height=”200px”}
勇者面前有一个大小为 3*3 的打地鼠游戏机，地鼠将随机出现在各个位置，moles[i] = [t,x,y] 表示在第 t 秒会有地鼠出现在
(x,y) 位置上，并于第 t+1 秒该地鼠消失。勇者有一把可敲打地鼠的锤子，初始时刻（即第 0 秒）锤子位于正中间的格子
(1,1)，锤子的使用规则如下： - 锤子每经过 1 秒可以往上、下、左、右中的一个方向移动一格，也可以不移动 -
锤子只可敲击所在格子的地鼠，敲击不耗时 请返回勇者最多能够敲击多少只地鼠。 注意： -
输入用例保证在相同时间相同位置最多仅有一只地鼠 示例 1： >输入： moles = [[1,1,0],[2,0,1],[4,2,2]] >

输出： 2 > >解释： >第 0 秒，锤子位于 (1,1) >第 1 秒，锤子移动至 (1,0) 并敲击地鼠 >第 2 秒，锤子移动至 (2,0)
第 3 秒，锤子移动至 (2,1) >第 4 秒，锤子移动至 (2,2) 并敲击地鼠 >因此勇者最多可敲击 2 只地鼠 示例 2：
输入：moles = [[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]] > >输出：3 > >解释： >第 0
秒，锤子位于 (1,1) >第 1 秒，锤子移动至 (2,1) 并敲击地鼠 >第 2 秒，锤子移动至 (1,1) >第 3 秒，锤子移动至 (1,0) >第
4 秒，锤子在 (1,0) 不移动并敲击地鼠 >第 5 秒，锤子移动至 (2,0) 并敲击地鼠 >因此勇者最多可敲击 3 只地鼠 示例 3：
输入：moles = [[0,1,0],[0,0,1]] > >输出：0 > >解释： >第 0 秒，锤子初始位于 (1,1)，此时并不能敲击
(1,0)、(0,1) 位置处的地鼠 提示： + 1 <= moles.length <= 10^5 + moles[i].length == 3 + 0 <= moles[i][0] <= 10^9 + 0 <= moles[i][1], moles[i][2] < 3

解法：DP

假设没有时间 0 出现的地鼠，记 f_i 表示考虑前 i 只地鼠，刚刚打完了第 i 只，最多能打中几只。转移即是枚举上一只打中的地鼠 j，那么从打中地鼠 j 到打中地鼠 i 经过的时间为 t = (t_i - t_j)，锤子需要移动的距离为 d = |x_i - x_j| + |y_i - y_j|。如果 t \ge d 就可以打完 j 再打 i。

朴素枚举 j 的复杂度是 \mathcal{O}(n^2) 的。由于棋盘是 3 \times 3 的，因此 d 最大值是 4，那么遇到 t > 4 的情况就直接用前缀 max 更新答案即可。由于每个时间每个位置最多一只地鼠，那么无法用前缀和更新的 j 与 i 的差距最大只有 4 \times 3 \times 3 = 36，这样就把复杂度降到了 \mathcal{O}(n)。

参考代码（c++）

class Solution {

public:
    int getMaximumNumber(vector<vector<int>>& moles) {
        // 把所有时间 0 出现的地鼠排除
        vector<vector<int>> A;
        bool flag = false;
        for (auto &mole : moles) {
            if (mole[0] == 0) {
                // 看一下有没有时间 0 位于 (1, 1) 的地鼠，一开始就能打
                if (mole[1] == 1 && mole[2] == 1) flag = true;
            } else {
                A.push_back(mole);
            }
        }
        // 初始位置位于 (1, 1)
        A.push_back(vector<int>{0, 1, 1});

        int n = A.size();
        sort(A.begin(), A.end());
        vector<int> f(n), g(n);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            f[i] = -1e8;
            for (int j = i - 1; j >= 0; j--) {
                int t = A[i][0] - A[j][0], d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2]);
                // 能从任何位置移过来，用前缀 max 更新答案
                if (t > 4) { f[i] = max(f[i], g[j] + 1); break; }
                // 虽然有时间限制，但移过来能来得及，更新答案
                else if (d <= t) f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
            g[i] = max(g[i - 1], f[i]);
        }
        return ans + (flag ? 1 : 0);
    }
};