Ошибка.
Попробуйте повторить позже
Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
Входные данные: В первой строке входного файла вводится одно число 
(натуральное число, не превышающее
) — количество ступенек. В следующей строке вводятся 
натуральных чисел, не превосходящих 
— стоимость
каждой ступеньки (снизу вверх).
Выходные данные: Выведите одно число — наименьшую возможную стоимость прохода по лесенке.
Выведите ответ для следующих чисел:
Жадный алгоритм на каждом шагу принимает локальное оптимальное решение, не заботясь о том, что будет дальше.
Разберём, почему в данной задаче жадный алгоритм не сработает. Изначально у него есть два варианта:
сходить на ступеньку с числом 
или с числом 
— и пойдет на ступеньку с числом 
, т.к. это дешевле. Но
правильное решение здесь — пойти на ступеньку с числом 
, потом мы сможем перепрыгнуть ступеньку с числом
.
Решим задачку ручками: 
+ 
= 
, а ступеньки с числами 
и 
мы перепрыгнули.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
