Лестница со стоимостью
Вы поднимаетесь по лестнице из
n ступеней. На каждом шаге вы можете подняться либо на 2 ступени, либо всего на 1. Когда вы встаете на очередную ступень, вы платите стоимость, связанную с ней. Ваша задача — добраться до самой вершины, заплатив как можно меньше.Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ 1000).В следующей строке записаны стоимости, соответствующие каждой ступени (0 ≤ ≤ 1000).
Выходные данные
Программа должна вывести минимальную сумму, которую нужно заплатить, чтобы оказаться на вершине лестницы.
Примеры
Входные данные | Выходные данные |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
Пояснение
- Мы находимся перед лестницей ⇒ текущая стоимость равна 0. Переходим сразу на вторую ступень ⇒ стоимость становится 12. Затем, сделав шаг длиной 2 ступени, выбираемся из лестницы ⇒ стоимость остаётся 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