«Лестница с призами». Робот начинает на полу с 0 очков. За прыжок он поднимается на одну или две ступеньки, но не может прыгать на две ступеньки два раза подряд. Число на перепрыгнутой ступеньке не учитывается. Нужно закончить движение на последней ступеньке и набрать как можно больше очков. Для каждой лестницы найдите максимальное количество очков: а) на 8 ступеньках снизу вверх написаны числа 5, −4, 6, 3, −7, 8, 2, 4; б) на 8 ступеньках снизу вверх написаны числа 4, −6, 7, −3, 9, −5, 8, 5.

Обозначим через A_i наибольшее число очков на ступеньке i, если последний прыжок был на одну ступеньку, а через B_i — если последний прыжок был на две. Тогда A_i = x_i + max(A_i−1, B_i−1), а B_i = x_i + A_i−2: перед прыжком на две ступеньки предыдущий прыжок не мог быть таким же.

а) Числа 5, −4, 6, 3, −7, 8, 2, 4.

Рассчитывая лучшие результаты для каждого способа последнего прыжка, получаем:

Ступенька: 1 2 3 4 5 6 7 8
A:   5 1 7 14 7 15 24 28
B:   — −4 11 4 0 22 9 19

Максимум на последней ступеньке: max(28, 19) = 28. Его даёт путь 1 → 3 → 4 → 6 → 7 → 8: 5 + 6 + 3 + 8 + 2 + 4 = 28. Два прыжка на две ступеньки подряд отсутствуют.

б) Числа 4, −6, 7, −3, 9, −5, 8, 5.

Расчёт:

Ступенька: 1 2 3 4 5 6 7 8
A:   4 −2 5 8 17 12 20 30
B:   — −6 11 −5 14 3 25 17

Максимум на последней ступеньке: max(30, 17) = 30. Его даёт путь 1 → 3 → 4 → 5 → 7 → 8: 4 + 7 − 3 + 9 + 8 + 5 = 30. Два прыжка на две ступеньки подряд отсутствуют.

Ответ: а) 28 очков; б) 30 очков.