1 条题解

  • 0
    @ 2026-11-12 21:58:27

    [Z] Frog 3(dp_z)题解

    题意简述

    NN 块石头高度严格递增。青蛙从 11 出发,可跳到任意更靠右的石头 jj,代价 (hj−hi)2+C(h_j-h_i)^2 + C。求到达 NN 的最小总代价。

    思路

    朴素 DP

    $$f_j = \min_{i<j}\left( f_i + (h_j-h_i)^2 + C \right).$$

    O(N2)O(N^2) 在 N=2×105N=2\times10^5 时不可行。

    斜率优化

    把式子展开:

    $$f_j = h_j^2 + C + \min_{i<j}\left( f_i + h_i^2 - 2h_i h_j \right).$$

    把每个 ii 看成一条直线

    $$y = m_i x + b_i,\qquad m_i = -2h_i,\quad b_i = f_i + h_i^2 + C,$$

    则 fj=hj2+min⁡i(mihj+bi)f_j = h_j^2 + \min_i (m_i h_j + b_i) —— 查询一组直线在 x=hjx = h_j 处的最小值。

    单调性

    • hih_i 严格递增 ⇒ 斜率 mi=−2him_i = -2h_i 严格递减;
    • 询问的 x=hjx = h_j 也严格递增。

    两者都单调 ⇒ 用一个单调队列维护下凸壳:队头弹出不再最优的直线,队尾维护凸性,每次 O(1)O(1) 摊还。

    整数运算

    ff 可达约 105×1012=101710^5\times10^{12} = 10^{17},h2h^2 项也在此量级,本解全部用 long long 整数 + __int128 判叉积,避免浮点误差。

    复杂度

    时间 O(N)O(N),空间 O(N)O(N)。

    参考代码

    #include <cstdio>
    using namespace std;
    typedef long long ll;
    typedef __int128 lll;
    
    int main() {
        int n; ll C;
        scanf("%d %lld", &n, &C);
        static ll h[200005], S[200005], B[200005], f[200005];
        for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
        int head = 0, tail = 0;
        f[1] = 0;
        // 转成求最大值:y = s_i * x + c_i, s_i = 2h_i, c_i = -(f_i + h_i^2 + C)
        S[tail] = 2 * h[1]; B[tail] = -(f[1] + h[1] * h[1] + C); tail++;
        for (int j = 2; j <= n; j++) {
            while (head + 1 < tail && S[head] * h[j] + B[head] <= S[head + 1] * h[j] + B[head + 1]) head++;
            f[j] = h[j] * h[j] - (S[head] * h[j] + B[head]);
            ll s = 2 * h[j], c = -(f[j] + h[j] * h[j] + C);
            while (tail - head >= 2) {
                ll s1 = S[tail - 2], c1 = B[tail - 2], s2 = S[tail - 1], c2 = B[tail - 1];
                if ((lll)(s - s2) * (c1 - c2) >= (lll)(c2 - c) * (s2 - s1)) tail--;
                else break;
            }
            S[tail] = s; B[tail] = c; tail++;
        }
        printf("%lld\n", f[n]);
        return 0;
    }
    

    易错点

    1. 代价是 (hj−hi)2+C(h_j-h_i)^2 + C,CC 是每次跳跃都加的,不是只加一次。
    2. 斜率与询问都单调时才能用单调队列;若 hh 非递增就需用 Li Chao 树或二分。
    3. 叉积要用 __int128,long long 相乘会溢出(h≤106h \le 10^6、f≤1017f\le10^{17} 量级)。
    4. 答案超过 int(样例 2 是 1.25×10121.25\times10^{12}),必须 long long;若用浮点会丢精度,别用 double。

    数据说明

    共 16 组:3 组官方样例(含 1.25×10121.25\times10^{12});N=2N=2 极值(hh 跨度 10610^6、C=1012C=10^{12} → 保证答案超 int64 需 long long);N=3N=3;N=5N=5;N=10N=10 随机;N=100/1000/104N=100/1000/10^4 随机;N=2×105N=2\times10^5 的等差 hh、随机 hh、含端点 11 与 10610^6 的随机 hh、C=1C=1 随机。

    • 1

    信息

    ID
    35
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    1
    已通过
    1
    上传者