Elearning CodePath – CTP Online Judge

FROG2

🟢 Easy

Có N hòn đá, được đánh số từ 1 đến N. Với mỗi chỉ số i, độ cao của hòn đá thứ i là h_i.

Ban đầu, một chú ếch đứng ở hòn đá thứ 1. Nếu đang đứng ở hòn đá i, chú có thể nhảy đến một trong các hòn đá:
$i+1, i+2, ..., i+K$
miễn là chỉ số hòn đá đích không vượt quá N.

Chi phí của một lần nhảy từ hòn đá i sang hòn đá j là:

$|h_i - h_j|$

Hãy tính chi phí nhỏ nhất để chú ếch đi từ hòn đá thứ 1 đến hòn đá thứ N.

Dữ liệu vào

| Thành phần | Mô tả |
|---|---|
| Dòng 1 | Hai số nguyên dương N và K |
| Dòng 2 | N số nguyên $h_1, h_2, \dots, h_N$ |

Ràng buộc

| Thành phần | Giới hạn |
|---|---|
| N | $2 \le N \le 10^5$ |
| K | $1 \le K \le 100 $|
| h_i | $1 \le h_i \le 10^4$ |

Kết quả ra

| Thành phần | Mô tả |
|---|---|
| Gồm 1 dòng | In ra chi phí nhỏ nhất để đi từ hòn đá 1 đến hòn đá N |

Ví dụ

| Input | Output | Giải thích |
|---|---|---|
| 5 3<br>10 30 40 50 20 | 30 | Một đường đi tối ưu là $1 \to 2 \to 5$. Chi phí là $abs(10-30)+abs(30-20)=30$. |
| 3 1<br>10 20 10 | 20 | Một đường đi tối ưu là $1 \to 2 \to 3$. Chi phí là $abs(10-20)+abs(20-10)=20$. |
| 2 100<br>10 10 | 0 | Một đường đi tối ưu là $1 \to 2$. Chi phí là $abs(10-10)=0$. |
| 10 4<br>40 10 20 70 80 10 20 70 80 60 | 40 | Một đường đi tối ưu là $1 \to 4 \to 8 \to 10$. Chi phí là $abs(40-70)+abs(70-70)+abs(70-60)=40$. |

Subtask

| Subtask | Ràng buộc | Tỷ lệ điểm |
|---|---|---|
| 1 | $N \le 1000$ | 30% |
| 2 | $N \le 10^4$ | 30% |
| 3 | Không có ràng buộc gì thêm | 40% |

✅ Đã AC: 1 / 1 submissions