Treppe mit Kosten
Du steigst eine Treppe mit
n Stufen hinauf. Bei jedem Schritt kannst du entweder zwei Stufen oder nur eine nehmen. Für jede Stufe, auf der du landest, fällt ein zugehöriger Kostenbetrag an. Dein Ziel ist es, mit möglichst geringen Gesamtkosten bis ganz nach oben zu gelangen.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 1000).Die nächste Zeile enthält die Kosten für jede Stufe (0 ≤ ≤ 1000).
Ausgabe
Das Programm soll die minimalen Kosten ausgeben, um die Treppe bis ganz nach oben zu erklimmen.
Beispiele
Eingabe | Ausgabe |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
Erläuterung
- Wir stehen am Fuß der Treppe ⇒ die aktuellen Kosten betragen 0. Wir steigen auf die zweite Stufe ⇒ die Kosten liegen bei 12. Anschließend setzen wir zu einem Zwei-Stufen-Schritt an und verlassen die Treppe ⇒ es bleibt bei den 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