Frog2
Xem dạng PDF
Gửi bài giải
Điểm:
14,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang 1 trong k hòn đá thứ i + 1, i + 2,...,i + k với chi phí nhảy là ~|h_i - h_j|~ với j là vị trí đáp của chú ếch.
Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.
Input
- Dòng đầu gồm n là số lượng hòn đá và số k ~(1 \le n \le 10^5, 1 \le k \le 100)~
- Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le hi \le 10^4)~
Output
- Gồm một dòng duy nhất là đáp án cần tìm
Examples
Input
5 3
10 30 40 50 20
Output
30
Input
3 1
10 20 10
Output
20
Note
Ở ví dụ 1 chú ếch sẽ nhảy 1 -> 2 -> 5 với chi phí là |10 - 30| + |30 - 20| = 30
Bình luận
de lam nhu frog 1 thoi
zipzip
ếch ộp
🐸