Задача Задача №3794129
А
А
2. Лягушонок Пене. Лягушонок Пене путешествует по виртуальному замку и собирает биткоины.
Запрос пользователя
Реши задание на изображении
Сверь числа и знаки с фото.
- Лягушонок Пене Лягушонок Пене путешествует по виртуальному замку и собирает биткоины. Схема виртуального замка и количество биткоинов в каждой комнате представлены на схеме: [Рисунок: в ромбовидной схеме сверху расположена комната start; от неё идут две стрелки: вниз-влево с подписью L и вниз-вправо с подписью R. Ниже по рядам расположены комнаты: 4, 2; 10, 8, 3; 36, 26, 27, 24; 14, 12, 14, 23, 16; 1, 3, 7, 4; 9, 10, 9; 12, 17. Внизу расположена комната finish.] От каждой комнаты, кроме крайних, существуют только два пути: налево (L) и направо (R), двигаться обратно через двери запрещено. Лягушонок начинает свой путь в самой верхней комнате, обозначенной словом start, а заканчивает — в комнате, обозначенной словом finish. Во всех комнатах, кроме начальной и конечной, лежат биткоины. Путешествуя по комнатам, лягушонок забирает себе все биткоины из каждой комнаты, которую посещает. Количество биткоинов указано на рисунке выше. Вам нужно определить и записать в первой строке ответа максимальное количество биткоинов, которые может собрать лягушонок Пене. Во второй строке необходимо записать маршрут, на котором он соберёт эту сумму. Маршрут состоит из букв L и R, записанных без разделителей. Например, если лягушонок сначала каждый раз будет входить в правую дверь (пока это возможно), а потом каждый раз будет входить в левую дверь, то ответом будет: 75 RRRRLLLL
Ответ: максимум — 96 биткоинов, маршрут — LRRRLLRL.
Оптимальный путь по комнатам:
start → 4 → 8 → 27 → 23 → 7 → 10 → 17 → finish
\[ 4+8+27+23+7+10+17=96. \]
Как получить ответ. Для каждой комнаты считаем лучшую сумму, с которой в неё можно прийти. Если в комнату \(v\) ведут два хода, то
\[ S(v)=b(v)+\max\{S(\text{сосед слева сверху}),\,S(\text{сосед справа сверху})\}. \]
Если сверху доступен только один сосед, берём его. Так перебирать все маршруты не нужно.
| Комнаты в ряду | Лучшие суммы прихода в них |
|---|---|
| 4, 2 | 4, 2 |
| 10, 8, 3 | 14, 12, 5 |
| 36, 26, 27, 24 | 50, 40, 39, 29 |
| 14, 12, 14, 23, 16 | 64, 62, 54, 62, 45 |
| 1, 3, 7, 4 | 65, 65, 69, 66 |
| 9, 10, 9 | 74, 79, 78 |
| 12, 17 | 91, 96 |
В комнату finish можно прийти из 12 или 17, поэтому максимум равен \(\max(91,96)=96\). Возвращаясь по лучшим переходам, получаем маршрут:
- start → 4: L
- 4 → 8: R
- 8 → 27: R
- 27 → 23: R
- 23 → 7: L
- 7 → 10: L
- 10 → 17: R
- 17 → finish: L
Итог: LRRRLLRL. Проверка суммы: \(4+8+27+23+7+10+17=96\).
