Escalier avec un coût
Vous devez gravir un escalier composé de
n marches. À chaque pas, vous pouvez choisir de monter soit de 2 marches, soit d’une seule. À mesure que vous posez le pied sur chaque marche, vous payez le coût associé à cette marche. Votre objectif est d’atteindre le sommet tout en payant le moins possible.Entrée
La première ligne de l'entrée contient un seul entier
n (1 ≤ n ≤ 1000).La ligne suivante contient les coûts associés à chaque marche (0 ≤ ≤ 1000).
Sortie
Le programme doit afficher le coût minimal pour atteindre le sommet de l’escalier.
Exemples
Input | Output |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
Explication
- Au départ, nous sommes devant l’escalier ⇒ le coût courant est 0. Nous grimpons sur la deuxième marche ⇒ le coût est 12. Ensuite, nous sortons de l’escalier en effectuant un pas de longueur 2 ⇒ le coût reste 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