1 条题解

  • 0
    @ 2026-11-12 21:39:51

    [B] Frog 2(dp_b)题解

    题意简述

    与 Frog 1 相同,但每次可跳 1∼K1 \sim K 格。

    思路

    状态与转移

    fif_i = 到达石头 ii 的最小代价。到达 ii 的最后一步可以来自任意 j∈[max⁡(1,i−K),i−1]j \in [\max(1, i-K), i-1]:

    $$f_i = \min_{j=\max(1,i-K)}^{i-1} \left( f_j + |h_i - h_j| \right).$$

    直接按这个式子做,每次枚举 KK 个前驱。

    为什么不需要更复杂的数据结构

    朴素的 O(NK)O(NK) 已是 105×100=10710^5 \times 100 = 10^7,完全够用。注意不要试图用单调队列优化——代价里带绝对值,最优前驱并不随 ii 单调,斜率优化也不适用(代价不是关于 hh 的二次函数)。

    复杂度

    时间 O(NK)≤107O(NK) \le 10^7,空间 O(N)O(N)。

    参考代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main() {
        int n, k;
        scanf("%d %d", &n, &k);
        static long long h[100005], f[100005];
        for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
        f[1] = 0;
        for (int i = 2; i <= n; i++) {
            f[i] = (1LL << 60);
            for (int j = max(1, i - k); j < i; j++)
                f[i] = min(f[i], f[j] + llabs(h[i] - h[j]));
        }
        printf("%lld\n", f[n]);
        return 0;
    }
    

    易错点

    1. 下界要写 max⁡(1,i−K)\max(1, i-K):i−Ki-K 可能 ≤0\le 0。
    2. 当 K≥N−1K \ge N-1 时可以一步从 11 跳到 NN,答案应为 ∣hN−h1∣|h_N-h_1|——用暴力样例可以验证(K=100,N=2K=100, N=2)。
    3. 初值不要用 0,要设成足够大的数,否则 min⁡\min 会被 00 污染。

    数据说明

    共 18 组:4 组官方样例;K=1K=1(退化为 Frog 1)、K≥N−1K\ge N-1、N=2N=2 极值、N=100/1000N=100/1000 随机;N=105N=10^5 时取 K=1,2,50,100K=1,2,50,100 各一组,另有大小交错的构造组,用于检验转移边界 max⁡(1,i−K)\max(1,i-K) 是否写对。

    • 1

    信息

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