小青蛙跳跳II
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