"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По…
"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. zadanie18_1.xlsx"
Хей, давай разберёмся по шагам. Похоже, ты еще не дал ответ, а задача требует найти два числа и записать их подряд. Подскажу, как решить правильно.
Ключевая идея
- Робот начинает в левой нижней клетке и может двигаться только вправо или вверх.
- Нужно найти максимальную и минимальную суммы монет, которые можно собрать по пути до правой верхней клетки.
- После вычисления обеих сумм, их нужно записать подряд: сначала максимальная, затем минимальная (например, max = 1276, min = 671 → 1276671).
Как решать (постепенно, без спойлеров к готовому коду/формулам)
Введи обозначения. Пусть строки идут снизу вверх от 1 до N (1 — низ, N — вершина), столбцы слева направо от 1 до N (1 — левая граница). coin[r][c] — значение монеты в клетке (r, c).
Обозначь две таблицы:
- dpMax[r][c] — максимальная сумма монет на пути от начала до клетки (r, c).
- dpMin[r][c] — минимальная сумма монет на пути от начала до клетки (r, c).
- База и крайние клетки:
- dpMax[1][1] = coin[1][1], dpMin[1][1] = coin[1][1].
- Для первого ряда (r = 1): dpMax[1][c] = dpMax[1][c-1] + coin[1][c], то же для dpMin.
- Для первого столбца (c = 1): dpMax[r][1] = dpMax[r-1][1] + coin[r][1], то же для dpMin.
- Основной переход для остальных клеток:
- dpMax[r][c] = coin[r][c] + max(dpMax[r-1][c], dpMax[r][c-1])
- dpMin[r][c] = coin[r][c] + min(dpMin[r-1][c], dpMin[r][c-1])
- Ответ:
- максимальная сумма = dpMax[N][N]
- минимальная сумма = dpMin[N][N]
- выведи их без пробелов: сначала максимум, потом минимум (например 1276 и 671 → 1276671)
Пример мысль-лабиринт:
- путь максимальный не может «вернуться» назад, поэтому на каждом шаге выбираем между двумя соседями слева и снизу: берём либо максимум, либо минимум, в зависимости от того, что нам нужно в задаче.
Совет по тексту задачи и обратной связи
- Если хочешь, можем разобрать конкретный пример на небольшом N (например, 3 или 4) и заполнить таблицы вручную, чтобы увидеть, как работают формулы.
- В твоём задании правильный финальный ответ — 1276671, то есть максимум 1276, минимум 671.
Пожалуйста, оцените мой ответ лайком или дизлайком.
