小青蛙跳跳II


Submit solution


Points: 300
Time limit: 1.0s
Memory limit: 8M

Author:
Problem type
Allowed languages
C, C++

https://atcoder.jp/contests/dp/tasks/dp_b
有 \(N\) 个台阶,编号为 \(1, 2, \dots, N\)。每个台阶 \(i\)(满足 \(1 \leq i \leq N\))的高度为 \(h_i\)。

一只青蛙一开始站在台阶 \(1\) 上。它要通过反复跳跃,最终跳到台阶 \(N\)。

每次在台阶 \(i\) 上时,青蛙可以跳到台阶 \(i+1, i+2, \dots, i+K\) 中的任意一个。
跳跃时需要花费的代价为跳出和跳入台阶高度差的绝对值,即从 \(i\) 跳到 \(j\) 的代价是:

\(\left|h_i-h_j \right|\)

请计算青蛙跳到台阶 \(N\) 所需要花费的最小总代价。

约束条件

所有输入均为整数。
\(2 \le N \le 10^5\)
\(1 \le K \le 100\)
\(1 \le h_i \le 10^4\)

输入格式

从标准输入中获取数据,格式如下:
N K
\(h_1 h_2 ... h_N\)

输出格式

输出青蛙跳到台阶
\(N\) 所需的最小总代价。


输入样例 1

5 3  
10 30 40 50 20

输出样例 1

30
说明

跳跃路径为台阶 1 → 2 → 5,总代价为:

\(\left|10-30 \right|+\left|30-20 \right|=20+10=30\)


输入样例 2

3 1  
10 20 10

输出样例 2

20
说明

跳跃路径为台阶 1 → 2 → 3,总代价为: \(\left|10-20 \right|+ \left|20-10 \right|=10+10=20\)


输入样例 3

2 100  
10 10

输出样例 3

0
说明

跳跃路径为台阶 1 → 2,代价为: \(\left|10-10 \right|=0\)


输入样例 4

10 4  
40 10 20 70 80 10 20 70 80 60

输出样例 4

40
说明

跳跃路径为台阶 1 → 4 → 8 → 10,总代价为: \(\left|40-70 \right|+ \left|70-70\right|+\left|70-60\right|=30+0+10=40\)


Comments

There are no comments at the moment.