953 . 過路費好貴
TopCoder
.jpg)
Tags
Description
德田高速公路上共有 $n$ 個收費站，且它們在路上按照順序排成一列。你要從德田高速公路的入口處（位於第 $1$ 個收費站之前）走到第 $n$ 個收費站，但你的錢包已經快見底了。每個收費站所收的過路費不盡相同，只要你離開收費站，就會被收取對應的金額。特別的是，你每次可以選擇往前走一個或兩個收費站。如果一次走兩個，被跳過的那個收費站不會收錢。現在，你想知道你所剩的錢到底夠不夠讓你抵達終點。請注意，當你到達第 $n$ 個收費站時，你不需要支付任何費用（費用是在離開收費站時收取的）。
Input Format
第一行有兩個整數 $n$ ，意義如題目所敘。
第二行有 $n$ 個整數 $c_1, c_2, ..., c_n$，分別代表第 $1$ 個到第 $n$ 個收費站所收的過路費。
- $1 \le n \le 10^ 6$
- $0 \le c_i \le 10^ 5$
Output Format
輸出一個整數，代表到達第 $n$ 個收費站所需的最少總過路費。
Sample Input 1
3 5 8 7
Sample Output 1
5
Sample Input 2
5 10 5 7 6 1
Sample Output 2
11
Hints
在範例１中，最佳的路徑是先走到第一個收費站，然後一次往前走兩個收費站，抵達第三個。
因為只有離開第一個收費站，所以總過路費是第一個收費站對應的５。
在範例２中，最佳的路徑是連續兩次往前走兩個收費站，再往前走一個，抵達第五個。
因為離開了第二、第四個收費站，所以總過路費是第二、第四個收費站對應的５＋６＝１１。
Problem Source
YTP 2025 高中組程式挑戰營 p3
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 0~19 | 無額外限制 | 10 |