Scala con un costo
Stai affrontando una scala composta da
n gradini. A ogni passo, hai la possibilità di salire di 2 gradini oppure di 1 solo. Ogni volta che metti piede su un gradino, devi pagare il costo associato a quel gradino. Il tuo obiettivo è arrivare in cima spendendo il meno possibile.Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 1000).La riga successiva contiene i costi associati a ciascun gradino (0 ≤ ≤ 1000).
Output
Il programma deve stampare il costo minimo per raggiungere la cima della scala.
Esempi
Ingresso | Uscita |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
Spiegazione
- Ci troviamo davanti alla scala ⇒ il costo corrente è 0. Scegliamo di salire direttamente sul secondo gradino ⇒ il costo diventa 12. Poi usciamo dalla scala con un salto di 2 gradini ⇒ il costo rimane 12.
- 1 20 1 1 1 20 1 2 20 1 ⇒
120 1 1 1 20 1 2 20 1 ⇒ 1 2011 1 20 1 2 20 1 ⇒ 1 20 1 1120 1 2 20 1 ⇒ 1 20 1 1 1 2012 20 1 ⇒ 1 20 1 1 1 20 1220 1 ⇒ 1 20 1 1 1 20 1 2 201⇒ 7
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB