A93766.跳石阶

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小青蛙准备从第 11 块石阶跳到第 nn 块。第 ii 块石阶的高度是 hih_i。
每次它可以从当前石阶跳到下一块(i→i+1i \to i+1)或隔一块(i→i+2i \to i+2)。
一次跳跃的体力消耗等于两块石阶高度差的绝对值:∣hx−hy∣\lvert h_x - h_y \rvert。

请你计算:从第 11 块跳到第 nn 块的最小总消耗。

输入格式

第一行:一个整数 nn。

第二行:nn 个整数,依次为 h1,h2,…,hnh_1, h_2, \dots, h_n。

输出格式

一行,一个整数,表示最小总消耗。

输入输出样例

  • 输入#1

    6
    30 10 60 10 60 50

    输出#1

    40

说明/提示

  • 1≤n≤1000001 \le n \le 100000

  • 0≤hi≤1090 \le h_i \le 10^9

对于样例:

一种最优方案:1→3→5→61 \to 3 \to 5 \to 6

消耗为 ∣30−60∣+∣60−60∣+∣60−50∣=30+0+10=40\lvert 30-60\rvert + \lvert 60-60\rvert + \lvert 60-50\rvert = 30+0+10=40。

输入解题思路,AI测评打分。不知道怎么写?

首页