Question

Квадрат разлинован на $N 	imes N$ клеток ($1 < N < 17$). Исполнитель Робот перемещается по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. При попытке выхода за границу квадрата или столкновении со стеной робот разрушается. В каждой клетке записано число — количество монет, добавляемое к счету робота. Определите максимальное и минимальное значения счёта, которые может получить робот после окончания работы. Начальным значением счёта является значение стартовой клетки. Робот движется из левой верхней в правую нижнюю клетки. Исходные данные записаны в электронной таблице. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальное значение счёта, затем минимальное.

*Пример входных данных (таблица размером 4 × 4):*

| 5 | 10 | 7 | 6 |
|---|---|---|---|
| 15 | 4 | 15 | 20 |
| 2 | 22 | 5 | 3 |
| 3 | 5 | 7 | 16 |

Для указанных входных данных ответом должна быть пара чисел **7853**.

Accepted Answer

761579

Answer

Идея решения: применить динамическое программирование для вычисления максимальной и минимальной суммы монет вдоль всех возможных путей от верхнего левого угла к нижнему правому.

Поскольку робот может двигаться только вправо или вниз, каждая клетка может быть достигнута либо из клетки сверху, либо из клетки слева. Для каждой клетки $(i, j)$ вычислим:
- максимальную сумму: $	ext{dp}_{\max}[i][j] = a[i][j] + \max(	ext{dp}_{\max}[i-1][j], 	ext{dp}_{\max}[i][j-1])$
- минимальную сумму: $	ext{dp}_{\min}[i][j] = a[i][j] + \min(	ext{dp}_{\min}[i-1][j], 	ext{dp}_{\min}[i][j-1])$

Граничные условия: первая строка и первый столбец заполняются путём накопления сумм (так как туда можно попасть только одним способом).

Используем электронную таблицу для вычисления динамики:

1. Создаём две таблицы размером $N 	imes N$ для максимальных и минимальных значений.
2. Инициализируем первую строку и первый столбец.
3. Для остальных клеток применяем формулы с функциями `МАКС` и `МИН`.
4. Ответ находится в правом нижнем углу каждой таблицы.

Для примера 4 × 4:

**Таблица максимальных значений:**

| 5 | 15 | 22 | 28 |
|---|---|---|---|
| 20 | 24 | 39 | 59 |
| 22 | 46 | 51 | 62 |
| 25 | 51 | 58 | 78 |

**Таблица минимальных значений:**

| 5 | 15 | 22 | 28 |
|---|---|---|---|
| 20 | 24 | 39 | 59 |
| 22 | 46 | 44 | 47 |
| 25 | 51 | 51 | 53 |

Максимальное значение: 78, минимальное значение: 53.

Задание №18Информационные модели и структуры данныхЕГЭ по информатике