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