Elearning CodePath – CTP Online Judge

FROG

🟢 Easy #Dynamic Programming

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 sang hòn đá i+1 hoặc i+2, với điều kiện 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 | Số nguyên dương N |
| 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 |
| 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 |
|---|---|---|
| 4<br>10 30 40 20 | 30 | Một cách đi tối ưu là 1 \to 2 \to 4, chi phí là $|10-30|+|30-20|=30$. |
| 2<br>10 10 | 0 | Một cách đi tối ưu là 1 \to 2, chi phí là $|10-10|=0$. |
| 6<br>30 10 60 10 60 50 | 40 | Một cách đi tối ưu là 1 \to 3 \to 5 \to 6, chi phí là $|30-60|+|60-60|+|60-50|=40$. |

Subtask

| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 30% | N \le 1000 |
| 2 | 70% | Không có ràng buộc gì thêm |

✅ Đã AC: 3 / 3 submissions