#AT1. Frog 1
Frog 1
[A] Frog 1(dp_a)
来源: AtCoder Educational DP Contest - Problem A 原题时限:2 秒 / 内存:1024 MB
题目描述
有 块石头,编号为 。
对于每个 (),第 块石头的高度为 。
有一只青蛙初始站在石头 上。它会重复下面的动作若干次,直到到达石头 :
- 若青蛙当前位于石头 ,则跳到石头 或石头 。此时需要支付代价 ,其中 是它落到的石头编号。
求青蛙到达石头 之前所需支付代价总和的最小值。
输入格式
输入由标准输入按以下格式给出:
N
h_1 h_2 \ldots h_N
输出格式
输出青蛙所需支付代价总和的最小值。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
4
10 30 40 20
输出:
30
样例 2
输入:
2
10 10
输出:
0
样例 3
输入:
6
30 10 60 10 60 50
输出:
40