每日算法 — 使用java实现打地鼠：斜率优化DP与凸包维护

可莉爸爸 AI算法

一、游戏场景：打地鼠其实是一道最优化题

街机厅里的打地鼠（Whac-A-Mole）看起来只是比谁手快：地鼠随机冒头，玩家在 3×3 的洞口间挥锤。但只要稍微认真地玩几局，就会发现它在决策层面有明确的结构：

  1. 时间窗口是硬的：一只地鼠只在 [t_i, t_i + τ] 之间可被打中，错过就没了；
  2. 挥锤是有代价的：锤子需要蓄能，蓄能越久，下一次挥出去的动能代价越大；
  3. 移动是有代价的：从一个洞口到另一个洞口需要位移时间，位移也会消耗蓄能；
  4. 收益不可简单相加：单次命中的价值取决于当时锤子处于什么蓄能状态。

把这四条翻译成数学形式，会得到一个非常典型的动态规划（DP）递推式；而这个递推式恰好具备决策点单调的结构，于是可以用斜率优化（Convex Hull Trick，简称 CHT）把 O(n²) 的转移压缩到 O(n)。本文用一个单线轨道的”机械打地鼠机”作为模型载体（地鼠沿一条传送带依次冒头，锤子沿轨道往复），完整实现这套决策算法。

二、把游戏抽象成递推式

2.1 数据与代价模型

设第 i 只地鼠冒头时刻为 t_i，价值为 v_i，洞口坐标为 x_i（沿轨道的整数坐标）。锤子有蓄能特性：连续两击之间，蓄能时长记为 t_i - t_j；同时位移距离 |x_i - x_j| 也要折算成等效的蓄能占用。定义动作代价前缀 S_i：

S_i = Σ_{k=1..i} [ (t_k - t_{k-1}) + λ · |x_k - x_{k-1}| ]

其中 S_0 = 0，t_0 = 0，x_0 = 0，λ 是位移折算系数。动能代价模型为：

E(j → i) = p · (S_i - S_j)² / q

为什么是平方？ 因为动能 E = ½ m ω²，锤头的角速度近似与蓄能时长成正比，所以代价对蓄能时长的依赖是二次的。这一点是整个算法能成立的关键：二次项展开后会退化成”一条直线”，而我们要做的正是在一堆直线里维护上包络。

2.2 递推式

令 dp[i] 表示「以第 i 只地鼠作为最后一击」时的最大净收益：

dp[i] = v_i + max_{0 ≤ j < i} { dp[j] - p·(S_i - S_j)²/q }

展开平方项：

dp[i] = v_i - p·S_i²/q + max_j { (dp[j] - p·S_j²/q) + (2p·S_j/q) · S_i }

2.3 直线化：平方项变成斜率

把 m_j = 2p·S_j/q 看作斜率、b_j = dp[j] - p·S_j²/q 看作截距，则右侧的 max 就是”在所有直线 L_j(x) = m_j·x + b_j 上，取 x = S_i 处的最大值”：

dp[i] = v_i - p·S_i²/q + max_j { m_j·S_i + b_j }

三条性质决定了算法选型：

  • 斜率单调：S_j 随 j 单调递增，所以 m_j 单调递增；
  • 查询单调：查询点 x = S_i 也单调递增；
  • 只增不删：我们只不断加入新直线，从不任意删除。

斜率单调 + 查询单调 = 标准的单调队列凸包，每次插入摊还 O(1)、每次查询摊还 O(1)，总复杂度 O(n)。

三、精度问题：不要用 double 存 DP

工程实现里最容易翻车的坑是精度。p·(S_i - S_j)²/q 是分数，用 double 存 DP 值时，误差会沿转移链累积，几百步后就可能把次优决策点误判为最优。

解决办法是整体消去分母：把所有 DP 值按 q 倍缩放，令 D[i] = dp[i]·q，于是递推式全整数：

D[i] = q·v_i + max_{0 ≤ j < i} { D[j] - p·(S_i - S_j)² }

对应直线参数变成 m_j = 2p·S_j、b_j = D[j] - p·S_j²、查询点 x = S_i，全部是 long。DP 值本身因此完全精确，唯一涉及”几何判断”的地方只剩”凸包里哪条直线该被淘汰”——那里我们用交叉相乘，并用 BigInteger 规避溢出。

四、Java 实现

4.1 项目结构

mole-hammer/
├── src/main/java/com/algodaily/mole/
│   ├── Mole.java              // 地鼠数据结构
│   ├── KineticModel.java      // 动能代价模型与前缀代价推导
│   ├── Plan.java              // 求解结果（收益 + 打击序列）
│   ├── ConvexHullPlanner.java // 单调队列凸包，O(n)
│   ├── LiChaoPlanner.java     // 李超树，O(n log n)，支持乱序/滑窗
│   ├── BruteForcePlanner.java // O(n²) 朴素 DP，对拍基准
│   └── HammerGameApp.java     // 入口：演示 + 随机对拍

4.2 数据结构与代价模型

package com.algodaily.mole;

/** 一只地鼠：冒头时刻、轨道坐标、命中价值 */
public final class Mole {
    public final long time;   // 冒头时刻 t_i（秒，整数）
    public final int x;       // 轨道坐标 x_i
    public final long value;  // 命中价值 v_i

    public Mole(long time, int x, long value) {
        this.time = time;
        this.x = x;
        this.value = value;
    }

    @Override
    public String toString() {
        return String.format("Mole(t=%d, x=%d, v=%d)", time, x, value);
    }
}

package com.algodaily.mole;

/**
 * 动能代价模型。
 * 把「蓄能时长」与「轨道位移」折算成严格递增的动作代价前缀 S_i，
 * 并保留动能系数的有理数形式 p/q，避免浮点误差。
 */
public final class KineticModel {
    public final long[] prefixCost; // S_0..S_n，严格递增
    public final int p;             // 动能系数分子
    public final int q;             // 动能系数分母

    public KineticModel(Mole[] moles, int p, int q, long moveCostPerUnit) {
        if (q <= 0) throw new IllegalArgumentException("q 必须为正");
        this.p = p;
        this.q = q;
        int n = moles.length;
        this.prefixCost = new long[n + 1];

        long acc = 0;
        for (int i = 0; i < n; i++) {
            // 蓄能耗时 = 与上一只地鼠的时间差（首只从 0 时刻起算）
            long dt = (i == 0) ? moles[0].time : moles[i].time - moles[i - 1].time;
            long dx = (i == 0) ? Math.abs(moles[0].x) : Math.abs(moles[i].x - moles[i - 1].x);
            acc += dt + moveCostPerUnit * dx; // 位移折算为等效蓄能时间
            prefixCost[i + 1] = acc;
        }
    }

    /** 打出第 i 只（1-based）时的前缀代价 S_i */
    public long s(int i) { return prefixCost[i]; }

    public int size() { return prefixCost.length - 1; }
}

package com.algodaily.mole;

/** 求解结果：缩放后的净收益（真实收益 = scaledProfit / q）+ 命中的地鼠下标序列 */
public final class Plan {
    public final long scaledProfit;
    public final int[] hits; // 1-based 地鼠下标，按打击顺序

    public Plan(long scaledProfit, int[] hits) {
        this.scaledProfit = scaledProfit;
        this.hits = hits;
    }

    public double profit(int q) { return (double) scaledProfit / q; }
}

4.3 单调队列凸包（核心，O(n)）

这个类同时承担两件事：维护上包络，以及在查询时一并返回最优值与给出它的决策下标，从而把”路径还原”也做到 O(1)。

package com.algodaily.mole;

import java.math.BigInteger;

/**
 * 单调队列维护上凸包（Convex Hull Trick），求 max(m_j * x + b_j)。
 *
 * 前提：斜率单调递增、查询 x 单调递增、只插入从不任意删除。
 * 单次插入摊还 O(1)，单次查询摊还 O(1)，整体 O(n)。
 */
public final class ConvexHullPlanner {

    /** 查询结果：最优值与该直线对应的 DP 决策下标 j */
    public static final class Hit {
        public final long value;
        public final int origin;
        Hit(long value, int origin) { this.value = value; this.origin = origin; }
    }

    private final long[] m;     // 斜率
    private final long[] b;     // 截距
    private final int[] origin; // 该直线来自哪个 j
    private int head = 0;       // 队首指针（当前最优直线）
    private int tail = 0;       // 队尾指针（下一个空槽）

    public ConvexHullPlanner(int capacity) {
        this.m = new long[capacity];
        this.b = new long[capacity];
        this.origin = new int[capacity];
    }

    /**
     * 判断 l2 是否被 l1、l3 完全遮蔽（上凸包语义）。
     * 交点 x12 = (b1 - b2) / (m2 - m1)，x23 = (b2 - b3) / (m3 - m2)；
     * 三条直线斜率递增，故两个分母均为正，交叉相乘不改变不等号方向：
     *   x12 >= x23  <=>  (b1 - b2)*(m3 - m2) >= (b2 - b3)*(m2 - m1)
     * 乘积量级可达 1e27，必须 BigInteger 才不溢出。
     */
    private static boolean redundant(long m1, long b1, long m2, long b2, long m3, long b3) {
        BigInteger left  = BigInteger.valueOf(b1 - b2).multiply(BigInteger.valueOf(m3 - m2));
        BigInteger right = BigInteger.valueOf(b2 - b3).multiply(BigInteger.valueOf(m2 - m1));
        return left.compareTo(right) >= 0;
    }

    /** 插入一条直线（斜率必须单调不降）；originIndex 用于回溯决策 */
    public void add(long slope, long intercept, int originIndex) {
        int pos = tail;

        // 同斜率：求 max 时只保留截距更大的那条
        if (pos > head && m[pos - 1] == slope) {
            if (b[pos - 1] >= intercept) return; // 新线更差，直接丢弃
            pos--;                              // 旧线更差，弹出后继续
        }
        // 维护上凸包：弹掉被完全遮蔽的直线
        while (pos - head >= 2
                && redundant(m[pos - 2], b[pos - 2], m[pos - 1], b[pos - 1], slope, intercept)) {
            pos--;
        }
        m[pos] = slope;
        b[pos] = intercept;
        origin[pos] = originIndex;
        tail = pos + 1;
    }

    /** 查询 x 处的最大值与决策下标（x 必须单调不降） */
    public Hit query(long x) {
        while (head + 1 < tail && m[head] * x + b[head] <= m[head + 1] * x + b[head + 1]) {
            head++; // 下一条直线在 x 处更优，队首永久失效
        }
        return new Hit(m[head] * x + b[head], origin[head]);
    }

    public boolean isEmpty() { return tail <= head; }
}

为什么 m*x+b 不会溢出？ 取 p ≤ 1000、S_n ≤ 10⁶，则 |m| = 2p·S ≤ 2·10⁹，|m·x| ≤ 2·10¹⁵；|b| = |D - p·S²| ≤ 10¹⁵。相加仍在 long（9.22·10¹⁸）的安全区内。但 redundant 的交叉乘积会到 10²⁷，所以那里单独用 BigInteger——这是”同一条式子里两处、量级完全不同”的典型例子。

4.4 主求解器

package com.algodaily.mole;

/** 用单调队列凸包求解打地鼠最优击打序列 */
public final class HammerSolver {

    public static Plan solve(Mole[] moles, KineticModel model) {
        int n = moles.length;
        long p = model.p, q = model.q;

        long[] D = new long[n + 1];    // D[i] = dp[i] * q
        int[] parent = new int[n + 1]; // 决策回溯指针
        ConvexHullPlanner hull = new ConvexHullPlanner(n + 1);

        D[0] = 0;
        parent[0] = -1;
        hull.add(0, 0, 0); // 起点直线：m = 2p*S_0 = 0，b = D[0] - p*S_0^2 = 0

        long bestScaled = 0; // 「一只都不打」的保底策略，收益为 0
        int bestIdx = 0;

        for (int i = 1; i <= n; i++) {
            long si = model.s(i);
            ConvexHullPlanner.Hit hit = hull.query(si);

            D[i] = q * moles[i - 1].value + hit.value - p * si * si;
            parent[i] = hit.origin;

            if (D[i] > bestScaled) {
                bestScaled = D[i];
                bestIdx = i;
            }
            // 当前状态作为新直线入包，供后续 i 使用
            hull.add(2 * p * si, D[i] - p * si * si, i);
        }
        return new Plan(bestScaled, restorePath(parent, bestIdx));
    }

    private static int[] restorePath(int[] parent, int end) {
        int len = 0;
        for (int k = end; k > 0; k = parent[k]) len++;
        int[] path = new int[len];
        for (int k = end, idx = len - 1; k > 0; k = parent[k]) path[idx--] = k;
        return path;
    }
}

一个容易忽略的细节：hull.add 必须在 query 之后。因为第 i 次查询只能用 j < i 的决策点，先把 i 自己插进去等于允许”原地连击”，会让 DP 出现自环。顺序错了不会报错，但答案会偏大——这类 bug 只能靠对拍抓出来。

4.5 李超树版本：支持乱序插入与滑窗约束

真实的打地鼠机常常有”蓄能上限”：两只地鼠如果隔太久，锤子蓄能溢出，这一击反而打不出去。可以给每只地鼠配置上限 A_i，于是合法决策集合变成滑动窗口 S_i - S_j ≤ A_i。此时”从队首永久出队”的规则不再成立（中间可能跳出一条还新鲜的直线），稳妥的替代是李超树（Li Chao Tree）：在离散化的 x = S_i 坐标上做插入 + 单点查询，O(log n)。

package com.algodaily.mole;

/**
 * 李超树（Li Chao Tree）：维护一堆直线，支持任意时刻插入、任意点查询最大值。
 * 所有比较都用 long 求值，天然精确；坐标在构造时离散化。
 * 相比单调队列凸包的优势：斜率无需单调、可叠加滑窗式过期过滤。
 */
public final class LiChaoPlanner {
    private static final long NEG = Long.MIN_VALUE / 4;

    private final long[] xs;       // 离散化后的查询点（单调递增）
    private final long[] slopes;
    private final long[] inters;
    private final boolean[] used;

    public LiChaoPlanner(long[] queryPoints) {
        long[] sorted = queryPoints.clone();
        java.util.Arrays.sort(sorted);
        this.xs = sorted;
        int size = 4 * Math.max(1, xs.length);
        this.slopes = new long[size];
        this.inters = new long[size];
        this.used = new boolean[size];
    }

    private long eval(long m, long b, long x) { return m * x + b; }

    public void add(long m, long b) { insert(1, 0, xs.length - 1, m, b); }

    private void insert(int node, int l, int r, long m, long b) {
        if (!used[node]) {
            used[node] = true;
            slopes[node] = m;
            inters[node] = b;
            return;
        }
        int mid = (l + r) >>> 1;
        long xl = xs[l], xm = xs[mid];
        long curM = slopes[node], curB = inters[node];

        // 先保证节点处保留「在 xm 上更优」的直线
        if (eval(m, b, xm) > eval(curM, curB, xm)) {
            slopes[node] = m; inters[node] = b;
            m = curM; b = curB;
        }
        if (l == r) return;

        // 再用左端点判断新线是否在左侧更优，决定往哪个子树下放
        if (eval(m, b, xl) > eval(slopes[node], inters[node], xl)) {
            insert(node << 1, l, mid, m, b);
        } else {
            insert(node << 1 | 1, mid + 1, r, m, b);
        }
    }

    public long query(long x) { return query(1, 0, xs.length - 1, lowerBound(x), x); }

    private long query(int node, int l, int r, int pos, long x) {
        long res = used[node] ? eval(slopes[node], inters[node], x) : NEG;
        if (l == r) return res;
        int mid = (l + r) >>> 1;
        if (pos <= mid) return Math.max(res, query(node << 1, l, mid, pos, x));
        return Math.max(res, query(node << 1 | 1, mid + 1, r, pos, x));
    }

    private int lowerBound(long x) {
        int lo = 0, hi = xs.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (xs[mid] < x) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

滑窗约束的落地：给 add 增加一个 expireAt 参数（该直线在 S 超过多少后失效），在 query 中若命中节点已过期就把贡献视为 NEG。李超树本身不支持删除，工程上通常两种做法：

  1. 惰性墓碑 + 双堆校验：查询时检查直线所有者 j 是否过期，过期则屏蔽该节点贡献；
  2. 时间分治（CDQ 分治）：把转移按时间轴切成 log n 段离线处理，每段用静态凸包，天然规避删除。

对本文这个尺度的游戏，方案 1 已经够用。

4.6 朴素 DP 对拍

package com.algodaily.mole;

/** O(n^2) 朴素 DP：正确性基准 */
public final class BruteForcePlanner {

    public static Plan solve(Mole[] moles, KineticModel model) {
        int n = moles.length;
        long[] D = new long[n + 1];
        int[] parent = new int[n + 1];
        D[0] = 0;
        parent[0] = -1;

        long best = 0;
        int bestIdx = 0;

        for (int i = 1; i <= n; i++) {
            long si = model.s(i);
            long bestCand = Long.MIN_VALUE / 4;
            int bestJ = 0;

            for (int j = 0; j < i; j++) {
                long d = si - model.s(j);
                long cand = D[j] - (long) model.p * d * d;
                if (cand > bestCand) { bestCand = cand; bestJ = j; }
            }
            D[i] = (long) model.q * moles[i - 1].value + bestCand;
            parent[i] = bestJ;

            if (D[i] > best) { best = D[i]; bestIdx = i; }
        }
        return new Plan(best, restore(parent, bestIdx));
    }

    private static int[] restore(int[] parent, int end) {
        int len = 0;
        for (int k = end; k > 0; k = parent[k]) len++;
        int[] path = new int[len];
        for (int k = end, idx = len - 1; k > 0; k = parent[k]) path[idx--] = k;
        return path;
    }
}

4.7 演示入口与随机对拍

package com.algodaily.mole;

import java.util.Arrays;
import java.util.Random;

/** 入口：先演示一局，再做 1000 组随机对拍 */
public final class HammerGameApp {

    public static void main(String[] args) {
        demoOneRound();
        stressTest();
    }

    private static void demoOneRound() {
        // 地鼠在 t=1..15 依次冒头，坐标沿轨道来回摆动
        Mole[] moles = {
                new Mole(1, 0, 30),
                new Mole(3, 2, 45),
                new Mole(4, 1, 12),
                new Mole(7, 5, 80),
                new Mole(9, 3, 25),
                new Mole(12, 6, 95),
                new Mole(15, 1, 40),
        };
        KineticModel model = new KineticModel(moles, 3, 2, 1L);

        Plan fast = HammerSolver.solve(moles, model);
        Plan slow = BruteForcePlanner.solve(moles, model);

        System.out.println("=== 单调队列凸包 O(n) ===");
        System.out.printf("净收益 = %.3f%n", fast.profit(model.q));
        System.out.println("打击序列 = " + Arrays.toString(fast.hits));

        System.out.println("=== 朴素 DP O(n^2) ===");
        System.out.printf("净收益 = %.3f%n", slow.profit(model.q));
        System.out.println("打击序列 = " + Arrays.toString(slow.hits));

        System.out.println("收益完全一致 = " + (fast.scaledProfit == slow.scaledProfit));
    }

    /** 随机对拍：验证凸包版本与朴素版本的缩放收益处处相同 */
    private static void stressTest() {
        Random rnd = new Random(20261101L);
        int mismatch = 0;

        for (int iter = 0; iter < 1000; iter++) {
            int n = 1 + rnd.nextInt(30);
            Mole[] moles = new Mole[n];
            long t = 0;
            for (int i = 0; i < n; i++) {
                t += 1 + rnd.nextInt(5); // 时间严格递增
                moles[i] = new Mole(t, rnd.nextInt(9), 5 + rnd.nextInt(100));
            }
            int p = 1 + rnd.nextInt(4);
            int q = 1 + rnd.nextInt(4);
            int lambda = rnd.nextInt(3);

            KineticModel model = new KineticModel(moles, p, q, lambda);
            long a = HammerSolver.solve(moles, model).scaledProfit;
            long b = BruteForcePlanner.solve(moles, model).scaledProfit;
            if (a != b) {
                mismatch++;
                System.out.println("不一致 iter=" + iter + " cht=" + a + " brute=" + b);
            }
        }
        System.out.println("对拍完成，不一致次数 = " + mismatch);
    }
}

跑一次，你会看到两个版本的收益完全相同：30 只地鼠时，朴素版做约 465 次转移，凸包版只做 30 次查询与 30 次插入。

五、复杂度与工程边界

方案 时间 空间 适用场景
朴素 DP O(n²) O(n) n ≤ 2000 的验证 / 对拍基准
单调队列凸包 O(n) 摊还 O(n) 斜率单调 + 查询单调 + 无删除
李超树 O(n log n) O(n) 斜率乱序，或叠加滑窗过期
CDQ 分治 + 静态凸包 O(n log² n) O(n) 带删除的离线版本

四条实现纪律：

  1. 斜率单调性是前提，不是巧合。如果地鼠冒头时间乱序，S_i 不再单调，单调队列会静默给出错误答案。判断依据就是 S 序列是否非降，这一步必须在建模时确认，而不是等出错后再调试。
  2. 分母必须提前消掉。p/q 的有理系数要在递推前乘到 D 上，否则 double 误差会在几百步后改变决策点。
  3. 溢出边界要算清。同一组式子里，m·x + b 是 10¹⁵ 量级（long 够用），而 redundant 的交叉乘积是 10²⁷ 量级（必须 BigInteger）。把这两处分开处理，别用一个”统一方案”糊过去。
  4. 插入与查询的顺序。add(i) 只能在 query(i) 之后，否则 DP 出现”原地连击”的自环。

六、这个模型能带到哪里

打地鼠只是一个载体，这套结构其实是”带二次代价的顺序决策“的通用模板：

  • 音游连击判定：连击间隔对分数的影响是二次衰减，dp 转移同样是平方代价，可直接套斜率优化；
  • 限时抢单 / 派单调度：骑手空驶成本按等待时长平方增长时，模型与本文同构；
  • 机器人的蓄能挥击：物理里 E = ½mω² 就是二次项，”动能预算下的动作排序”本质都是同一个凸包。

理解”为什么平方项能变成一条直线”比记住凸包模板更重要：只要代价对决策变量的依赖能被拆成 x 的线性组合，max 就变成了”在一堆直线上取包络”——这就是斜率优化的全部秘密。

Tagged with: