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

Обозначим через А_i наибольшее число очков при попадании на ступеньку i прыжком на одну ступеньку, а через Б_i — прыжком на две. Чтобы не делать два прыжка на две ступеньки подряд, для второго случая учитываем только путь, где предыдущий прыжок был на одну ступеньку.

а) Числа на ступеньках: 5, −4, 6, 3, −7, 8, 2, 4.

Считаем лучшие очки для каждого способа попасть на ступеньку:

1-я: А₁ = 5.

2-я: А₂ = 5 − 4 = 1; Б₂ = −4.

3-я: А₃ = max(1, −4) + 6 = 7; Б₃ = 5 + 6 = 11.

4-я: А₄ = max(7, 11) + 3 = 14; Б₄ = 1 + 3 = 4.

5-я: А₅ = max(14, 4) − 7 = 7; Б₅ = 7 − 7 = 0.

6-я: А₆ = max(7, 0) + 8 = 15; Б₆ = 14 + 8 = 22.

7-я: А₇ = max(15, 22) + 2 = 24; Б₇ = 7 + 2 = 9.

8-я: А₈ = max(24, 9) + 4 = 28; Б₈ = 15 + 4 = 19.

На последней ступеньке можно набрать max(28, 19) = 28 очков.

б) Числа на ступеньках: 4, −6, 7, −3, 9, −5, 8, 5.

1-я: А₁ = 4.

2-я: А₂ = 4 − 6 = −2; Б₂ = −6.

3-я: А₃ = max(−2, −6) + 7 = 5; Б₃ = 4 + 7 = 11.

4-я: А₄ = max(5, 11) − 3 = 8; Б₄ = −2 − 3 = −5.

5-я: А₅ = max(8, −5) + 9 = 17; Б₅ = 5 + 9 = 14.

6-я: А₆ = max(17, 14) − 5 = 12; Б₆ = 8 − 5 = 3.

7-я: А₇ = max(12, 3) + 8 = 20; Б₇ = 17 + 8 = 25.

8-я: А₈ = max(20, 25) + 5 = 30; Б₈ = 12 + 5 = 17.

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