#AT1. Frog 1

Frog 1

[A] Frog 1(dp_a)

来源: AtCoder Educational DP Contest - Problem A 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 块石头,编号为 1,2,…,N1, 2, \ldots, N。

对于每个 ii(1≤i≤N1 \le i \le N),第 ii 块石头的高度为 hih_i。

有一只青蛙初始站在石头 11 上。它会重复下面的动作若干次,直到到达石头 NN:

  • 若青蛙当前位于石头 ii,则跳到石头 i+1i+1 或石头 i+2i+2。此时需要支付代价 ∣hi−hj∣|h_i - h_j|,其中 jj 是它落到的石头编号。

求青蛙到达石头 NN 之前所需支付代价总和的最小值。

输入格式

输入由标准输入按以下格式给出:

N
h_1 h_2 \ldots h_N

输出格式

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

数据范围

  • 输入中的所有值均为整数。
  • 2≤N≤1052 \le N \le 10^5
  • 1≤hi≤1041 \le h_i \le 10^4

样例 1

输入:

4
10 30 40 20

输出:

30

样例 2

输入:

2
10 10

输出:

0

样例 3

输入:

6
30 10 60 10 60 50

输出:

40