Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №2

Просмотров 8 Комментарии 0

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.

Входные данные: В первой строке входного файла вводится одно число $N$ (натуральное число, не превышающее $100$ ) — количество ступенек. В следующей строке вводятся $N$ натуральных чисел, не превосходящих $100$ — стоимость каждой ступеньки (снизу вверх).

Выходные данные: Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Выведите ответ для следующих чисел:

$4$

$1$ $2$ $10$ $2$

Жадный алгоритм на каждом шагу принимает локальное оптимальное решение, не заботясь о том, что будет дальше. Разберём, почему в данной задаче жадный алгоритм не сработает. Изначально у него есть два варианта: сходить на ступеньку с числом $1$ или с числом $2$ — и пойдет на ступеньку с числом $1$ , т.к. это дешевле. Но правильное решение здесь — пойти на ступеньку с числом $2$ , потом мы сможем перепрыгнуть ступеньку с числом $10$ .

Решим задачку ручками: $2$ + $2$ = $4$ , а ступеньки с числами $1$ и $10$ мы перепрыгнули.

Ответ: 4