ЕГЭ · ЗАДАНИЕ 18
Робот, таблицы и динамика · практика 18
В файле квадратная таблица 6×6 положительных чисел. Робот идёт из левой верхней клетки в правую нижнюю, только вправо или вниз. Собирает числа всех посещённых клеток, включая начальную и конечную. Найдите максимальную сумму.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Файлы к заданию
ege-18-checkpoint-9.txtИсточник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 188
Решение по шагам
- В клетку можно прийти только сверху или слева. Обозначим D[i][j] максимальную сумму до неё, включая её число.
- В начальной клетке D равно её числу. Первую строку и столбец заполняем накопленной суммой. В остальных клетках: D[i][j]=a[i][j]+max(D[i−1][j],D[i][j−1]).
- Получится таблица лучших сумм ниже. Правая нижняя клетка даёт ответ 188.
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 1 | 3 | 27 | 52 | 57 | 68 |
| 20 | 32 | 47 | 77 | 89 | 109 |
| 46 | 75 | 89 | 104 | 128 | 154 |
| 73 | 78 | 109 | 125 | 152 | 174 |
| 75 | 95 | 131 | 156 | 168 | 182 |
| 84 | 116 | 136 | 164 | 175 | 188 |
Проверка на Python
a = [list(map(int, line.split())) for line in open("ege-18-checkpoint-9.txt")]
n = len(a)
dp = [row[:] for row in a]
for i in range(n):
for j in range(n):
previous = []
if i > 0: previous.append(dp[i - 1][j])
if j > 0: previous.append(dp[i][j - 1])
if previous: dp[i][j] += max(previous)
print(dp[-1][-1])