3 Главная идея — таблица сумм

Главная идея — таблица сумм

Робот приходит в клетку либо сверху, либо слева. Значит, наибольшая сумма в клетке — это её монета плюс больший из двух соседей (сверху или слева), в которых сумма уже посчитана. Заполняем поле сумм слева направо и сверху вниз — и в конечной клетке получаем ответ.

Иллюстрация к заданию 18, рисунок 1Иллюстрация к заданию 18, рисунок 2

Слева — исходное поле с монетами (жирные линии — стены). Справа — таблица сумм: в каждой клетке записана наибольшая сумма, с которой в неё можно прийти. В правой нижней клетке — 25, это и есть максимум.

Формула для каждой клетки:

Сумма = монета + максимум( сумма сверху , сумма слева )

  • Верхняя левая клетка (старт) = просто её монета.

  • Верхняя строка: приходить можно только слева → монета + сосед слева.

  • Левый столбец: только сверху → монета + сосед сверху.

📌 Стена «отрезает» соседа

Если между клеткой и соседом стоит стена, из этого соседа прийти нельзя — в формуле его не учитываем. Если стена слева — берём только соседа сверху; если сверху — только слева. Если клетка отрезана с двух сторон — в неё Робот не попадёт.

Главная идея — таблица сумм — Задание 18 ЕГЭ 2027 | Методички — Профиматика