Динамическое программирование: Робот-сборщик монет
Задание 18 · Билет 2 · ЕГЭ по информатике
Условие
Задание выполняется с использованием прилагаемого файла. Поле разлиновано на N×N клеток. Робот перемещается только вправо или вниз; поле и часть клеток разделены стенами, сквозь которые пройти нельзя. В каждой клетке лежит монета достоинством от 1 до 100. Конечная клетка — та, справа и снизу от которой стена.
Определите максимальную и минимальную денежные суммы среди всех итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную.
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
На рисунке — пример входных данных (4×4). Толстыми линиями обозначены стены; в файле поле другого размера.
Потренируйся на поле со стенами: найди максимальную и минимальную суммы накопленных монет — от разминки до формата экзамена.
Решение
Решение
шагов: 5 из 5Откройте файл
Скачайте task18-2-robot.ods и откройте в LibreOffice Calc. Поле — N×N клеток; толстые линии между клетками — стены, внешняя рамка — тоже стена.
Считайте суммы по клеткам
Заведите вторую таблицу и заполните её: сумма = монета + МАКС(сверху; слева), беря только соседей без стены между вами. Стартовая клетка — сама монета; соседа за стеной в формулу не ставьте.
Заполните по порядку и сделайте минимум
Идите слева-направо и сверху-вниз, протягивая формулу (маркер или Ctrl+D) и поправляя клетки у стен. Для минимума сделайте такую же таблицу с МИН.
Конечные клетки
Отметьте клетки, у которых справа и снизу стена, и выпишите их суммы.
Проверьте ответ
Для этого билета получается 2018 103. Пересчитайте пару клеток вручную для проверки.
Теория и другие билеты
Разбор с нуля, типовые ошибки, частые вопросы и все билеты задания 18 — на странице задания.