1 条题解

  • 1
    @ 2026-11-12 21:39:13

    [A] Frog 1(dp_a)题解

    题意简述

    一排 NN 块石头,高度 hih_i。青蛙从 11 出发,每次可跳 11 或 22 格,落到石头 jj 的代价为 ∣hi−hj∣|h_i-h_j|,求到达 NN 的最小总代价。

    思路

    状态与转移

    唯一需要知道的信息是"现在站在哪块石头上",于是设 fif_i 为从石头 11 跳到石头 ii 的最小总代价。到达 ii 只能从 i−1i-1 或 i−2i-2 跳来:

    f1=0,f2=∣h2−h1∣,f_1 = 0,\qquad f_2 = |h_2-h_1|, $$f_i = \min\left(f_{i-1} + |h_i - h_{i-1}|,\; f_{i-2} + |h_i - h_{i-2}|\right)\quad (i \ge 3).$$

    答案是 fNf_N。

    为什么正确

    任何一条到达 ii 的路径,其最后一步必然从 i−1i-1 或 i−2i-2 出发;而到达 i−1i-1(或 i−2i-2)的最优代价与之后怎么跳无关(无后效性)。因此把两种情况的"最优前驱"都试一遍取最小即可。

    复杂度

    时间 O(N)O(N),空间 O(N)O(N)(可优化到 O(1)O(1))。

    参考代码

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

    易错点

    1. N≥2N \ge 2 是题目保证的,但仍建议对 N=1N=1 特判(不跳,代价 00),否则 f[2] 越界。
    2. ff 的值最大约 105×104=10910^5 \times 10^4 = 10^9,int 勉强够用,但习惯上开 long long 更安全。
    3. 初始化 ff 时别把 f1f_1 写成 h1h_1——题目只计算跳跃的代价,起点高度不计入。

    数据说明

    共 16 组:前 3 组为官方样例;另有 N=2N=2 的两个极值(1→1041\to10^4 与反向)、全等高(答案 00)、单调递增/递减、大小交错、N=100/1000N=100/1000 随机、N=105N=10^5 的随机/全同/递增/全 10410^4 等,用于卡住"只跳 1 格"与"只跳 2 格"的错误贪心。

    • 1

    信息

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