Atcoder Educational DP Contest B - Frog 2

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ hòn đá, được đánh số từ ~1~ đến ~N~. Với mỗi chỉ số ~i~ ~(1 \le i \le N)~, độ cao của hòn đá thứ ~i~ là ~h_{i}~

Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện liên tục một loạt các hành động sau:

  • Nếu chú đang ngồi ở hòn đá ~i~ chú có thể nhảy đến các hòn đá thứ ~i+1~, ~i+2~ ~...~ ~i + K~. Chú sẽ mất phí khi nhảy là ~|h_{i} - h_{j}|~ với ~j~ là hòn đá mà chú ếch nhảy đến.

Bạn hãy giúp chú ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ ~N~ nhé.

Input

  • Dòng đầu tiên của dữ liệu vào chứa hai số nguyên dương ~N~ và ~K~ ~(2 \le N \le 10^{5}, 1 \le K \le 100)~, lần lượt là số lượng hòn đá và giới hạn nhảy của ếch.
  • Dòng thứ hai gồm ~N~ số nguyên ~h_{i}~ ~(1 \le i \le N, 1 \le h_{i} \le 10^{4})~, là độ cao của hòn đá thứ ~i~.

Output

  • Gồm một số nguyên, là chi phí ít nhất để nhảy từ hòn đá thứ nhất đến hòn đá thứ ~N~.

Sample 1

Input
5 3
10 30 40 50 20
Output
30
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 5~. Chi phí sẽ là ~|10 - 30| + |30 - 20| = 30~.

Sample 2

Input
3 1
10 20 10
Output
20
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 3~. Chi phí sẽ là ~|10 - 20| + |20 - 10| = 20~.

Sample 3

Input
2 100
10 10
Output
0
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 2~. Chi phí sẽ là ~|10 - 10|= 0~.

Sample 4

Input
10 4
40 10 20 70 80 10 20 70 80 60
Output
40
Giải thích

Một đường đi tối ưu là: ~1 \rightarrow 4 \rightarrow 8 \rightarrow 10~. Chi phí sẽ là ~|40−70|+|70−70|+|70−60|=40~.


Comments

Please read the guidelines before commenting.