Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

---

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, \ldots, 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é.

Dữ liệu vào

• 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~.

Kết quả

• 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 Input 1

5 3
10 30 40 50 20

Sample Output 1

30

Giải thích

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

Sample Input 2

3 1
10 20 10

Sample Output 2

20

Giải thích

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

Sample Input 3

2 100
10 10

Sample Output 3

0

Giải thích

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

Sample Input 4

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

Sample Output 4

40

Giải thích

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

Nguồn: AtCoder Educational DP Contest B (VNOJ).