Условие
Квадрат разлинован на 5 × 5 клеток. В каждой клетке лежит монета (таблица ниже, строки сверху вниз, столбцы слева направо):
Исполнитель Робот стартует из левой верхней клетки. За одно перемещение он может перейти в соседнюю клетку вправо или вниз. Робот заканчивает движение в правой нижней клетке. Посетив клетку (включая начальную и конечную), Робот забирает монету.
1) Найдите максимальную сумму монет на маршруте Робота.
2) Найдите количество клеток с монетой строго больше 30 на оптимальном маршруте.
В ответе запишите два числа через пробел.
| 10 | 25 | 30 | 15 | 20 |
| 40 | 15 | 45 | 20 | 35 |
| 20 | 50 | 25 | 40 | 15 |
| 35 | 20 | 55 | 30 | 25 |
| 15 | 45 | 20 | 60 | 50 |
Исполнитель Робот стартует из левой верхней клетки. За одно перемещение он может перейти в соседнюю клетку вправо или вниз. Робот заканчивает движение в правой нижней клетке. Посетив клетку (включая начальную и конечную), Робот забирает монету.
1) Найдите максимальную сумму монет на маршруте Робота.
2) Найдите количество клеток с монетой строго больше 30 на оптимальном маршруте.
В ответе запишите два числа через пробел.
Решение
grid = [[10,25,30,15,20],[40,15,45,20,35],
[20,50,25,40,15],[35,20,55,30,25],
[15,45,20,60,50]]
n = 5
dp = [[0]*n for _ in range(n)]
dp[0][0] = grid[0][0]
for j in range(1,n): dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1,n): dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,n):
for j in range(1,n):
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
print(dp[4][4]) # 340
# Восстановление пути
i, j = 4, 4; path = [(4,4)]
while i or j:
if i==0: j-=1
elif j==0: i-=1
elif dp[i-1][j]>=dp[i][j-1]: i-=1
else: j-=1
path.append((i,j))
path.reverse()
# Путь: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)→(3,2)→(3,3)→(4,3)→(4,4)
# Монеты: 10,40,20,50,25,55,30,60,50 → сумма=340
count = sum(1 for r,c in path if grid[r][c]>30)
print(count) # 5
Оптимальный путь содержит монеты: 10, 40, 20, 50, 25, 55, 30, 60, 50.Сумма = 340; клеток с монетой > 30: 5 (40, 50, 55, 60, 50).
Ответ:340 5