Nguồn: Đề thi tuyển sinh vào lớp 10 THPT chuyên tỉnh Kiên Giang năm học 2024-2025

Nhân kỷ niệm ngày thành lập Đoàn, giáo viên Tổng phụ trách tổ chức 1 trò chơi có thưởng cho các bạn lớp 9 như sau: Có N ô vuông được vẽ thẳng hàng trên sân trường, các ô vuông được đánh số từ 1, 2, …, N. Mỗi ô vuông thứ i (1 ≤ i ≤ N) có giá trị năng lượng là hᵢ. Một bạn học sinh đang ở ô vuông thứ i, có thể di chuyển tới ô vuông thứ j (i+1 ≤ j ≤ i+K) tiếp theo như sau:

• Một lần di chuyển được xác định là một bước nhảy từ ô vuông thứ i đến ô vuông thứ j. Chi phí năng lượng của bạn học sinh tiêu hao cho 1 lần di chuyển là |hⱼ − hᵢ| với hᵢ, hⱼ là giá trị năng lượng tại ô i, j.

• Bạn học sinh nào di chuyển từ ô số 1 đến ô số N với tổng chi phí năng lượng thấp nhất sẽ được thưởng 1 phần quà.

Yêu cầu: Hãy tìm tổng chi phí năng lượng thấp nhất để giúp bạn học sinh di chuyển từ ô vuông số 1 đến ô vuông thứ N.

Dữ liệu vào:

• Dòng đầu ghi 2 số N và K cách nhau một ký tự trắng; N là số ô vuông (2 ≤ N ≤ 10⁵), K là số ô vuông tối đa bạn học sinh có thể di chuyển qua (1 ≤ K ≤ 100).

• Dòng thứ hai chứa N giá trị hᵢ (1 ≤ hᵢ ≤ 100), mỗi số cách nhau một ký tự trắng là chi phí năng lượng của ô vuông thứ i tương ứng.

Dữ liệu ra: Ghi một số là tổng chi phí năng lượng thấp nhất.

Ví dụ:

Ràng buộc:

- Có 80% các test có (2 ≤ N ≤ 10³).

- Có 20% các test có (10³ < N ≤ 10⁵).