Vượt suối 2

Xem dạng PDF

Gửi bài giải

Điểm: 0,30 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Problem type
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Tí muốn vượt qua một con suối bằng cách nhảy từ viên đá này sang viên đá khác. Trước mặt Tí là một hàng n viên đá, mỗi viên đá thứ i có độ cao là hi.

Tí bắt đầu từ viên đá đầu tiên. Tại mỗi viên đá thứ i, Tí có thể chọn nhảy tới một trong k viên đá tiếp theo: i+1, i+2, ..., i+k. Mỗi cú nhảy từ viên đá i sang viên đá j có một chi phí được tính bằng |hihj|, với j là viên đá mà Tí đáp xuống.

Nhiệm vụ của bạn là giúp Tí tìm con đường có tổng chi phí ít nhất để vượt qua suối và đến được viên đá thứ n.

Input

  • Dòng đầu tiên gồm hai số nguyên nk, trong đó:

    • n là số lượng viên đá (1n105).
    • k là số viên đá mà Tí có thể nhảy tới trong một lần (1k100).
  • Dòng thứ hai chứa n số nguyên, trong đó số thứ i là chiều cao hi của viên đá thứ i (1hi104).

Output

  • In ra một số nguyên duy nhất là chi phí nhỏ nhất để Tí có thể tới được viên đá thứ n.

Sample Test

Input 1
Copy
5 3
10 30 40 50 20
Output 1
Copy
30
Input 2
Copy
3 1
10 20 10
Output 2
Copy
20

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.