Chi phí tối thiểu leo cầu thang
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho mảng $C$ gồm $N$ số nguyên không âm, trong đó $C_i$ là chi phí phải trả khi bước lên bậc thang thứ $i$ ($1 \le i \le N$). Sau khi trả chi phí ở bậc $i$, bạn có thể bước tiếp $1$ hoặc $2$ bậc. Bạn có thể bắt đầu từ bậc $1$ hoặc bậc $2$, và mục tiêu là vượt qua bậc $N$ (tức là đến vị trí $N+1$).
Hãy tìm tổng chi phí nhỏ nhất để hoàn thành cầu thang.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $C_1, C_2, \dots, C_N$ ($0 \le C_i \le 10^4$).
Dữ liệu ra
Một số nguyên duy nhất là tổng chi phí tối thiểu.
Ví dụ
| Input | Output |
|---|---|
3<br>10 15 20 |
15 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le C_i \le 10^4$
Community Discussion