AT_dp_a Frog 1

题目描述

有 $N$ 个台阶。每个台阶编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N$），第 $i$ 个台阶的高度为 $h_i$。

一只青蛙最初在第 $1$ 个台阶上。青蛙可以重复以下操作，试图到达第 $N$ 个台阶：

• 当青蛙在第 $i$ 个台阶时，可以跳到第 $i+1$ 或第 $i+2$ 个台阶。跳到目标台阶 $j$ 时，需要支付的代价为 $|h_i - h_j|$。

请你求出青蛙到达第 $N$ 个台阶所需支付的总代价的最小值。

输入格式

输入通过标准输入按以下格式给出。

$N$ $h_1$ $h_2$ $\ldots$ $h_N$

输出格式

输出青蛙需要支付的总代价的最小值。

输入输出样例 #1

输入 #1

4
10 30 40 20

输出 #1

30

输入输出样例 #2

输入 #2

2
10 10

输出 #2

0

输入输出样例 #3

输入 #3

6
30 10 60 10 60 50

输出 #3

40

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq h_i \leq 10^4$

样例解释 1

如果青蛙按 $1 \to 2 \to 4$ 的顺序移动，则总代价为 $|10 - 30| + |30 - 20| = 30$。

样例解释 2

如果青蛙按 $1 \to 2$ 的顺序移动，则总代价为 $|10 - 10| = 0$。

样例解释 3

如果青蛙按 $1 \to 3 \to 5 \to 6$ 的顺序移动，则总代价为 $|30 - 60| + |60 - 60| + |60 - 50| = 40$。

由 ChatGPT 4.1 翻译