Задание 18 ЕГЭ по информатике. Жадные алгоритмы

Принцип динамического программирования

Принцип оптимальности пути: любая часть оптимального пути — оптимальна. Это позволяет считать оптимальные значения для каждой клетки/состояния «снизу-вверх» и использовать их дальше.

Простой случай: робот по полю вправо/вниз, максимум монет

Задача: робот идёт по клетчатому полю из левого верхнего угла в правый нижний. В каждой клетке лежит заданное количество монет. Найти путь из A1 в C3, при котором сумма монет максимальна. Разрешённые шаги: на одну клетку вправо или вниз.

Идея решения (таблица максимумов)

• Строим вспомогательную таблицу: в каждой клетке — наибольшее число монет, которое можно собрать из стартовой клетки A1 в текущую. Проходим построчно сверху вниз. Текущую клетку выделяем жирно (в презентации).
• A1: в стартовой клетке 63 монеты — столько и «накопили».
• B1: только из A1 ⇒ 63+78=141.
• C1: только из B1 ⇒ 141+58=199.
• A2: только из A1 ⇒ 63+10=73.
• B2: из A2 (73+1=74) и из B1 (141+1=142) — берём максимум ⇒ 142.
• C2: из B2 (142+42=184) и из C1 (199+42=241) — максимум ⇒ 241.
• A3: только из A2 ⇒ 73+25=98.
• B3: из A3 (98+29=127) и из B2 (142+29=171) — максимум ⇒ 171.
• C3 (финиш): из B3 (171+87=258) и из C2 (241+87=328) — максимум ⇒ 328.

Шаблон переходов (максимум)

Если разрешены шаги вправо и вниз, то для клетки (i,j) (1-индексация) верно:

best[i][j] = coins[i][j] + max(best[i-1][j], best[i][j-1])

Границы (первая строка/столбец) — сумма по единственно возможному пути.

Примеры решений заданий

Задание 1. Классический квадрат N×N, шаги вправо/вниз: максимальная и минимальная суммы монет

Условие: квадрат N×N (1<N<17), шаги на одну клетку вправо/вниз, при выходе за границу — разрушение. В каждой клетке монета 1..100. Посетив клетку, робот забирает монету (включая старт и финиш). Найти максимальную и минимальную сумму на пути из левого верхнего в правый нижний.

Это слайд-шоу требует JavaScript.

DP-формулы

max[i][j] = coins[i][j] + max(max[i-1][j], max[i][j-1])
min[i][j] = coins[i][j] + min(min[i-1][j], min[i][j-1])

Инициализация: max[1][1]=min[1][1]=coins[1][1]; дальше — по первой строке/столбцу накапливаем суммы. Ответы: max[N][N] и min[N][N].

def solve_min_max(coins):
    n=len(coins)
    INF=10**9
    mx=[[0]*n for _ in range(n)]
    mn=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            v=coins[i][j]
            if i==0 and j==0: mx[i][j]=mn[i][j]=v
            elif i==0:         mx[i][j]=mx[i][j-1]+v; mn[i][j]=mn[i][j-1]+v
            elif j==0:         mx[i][j]=mx[i-1][j]+v; mn[i][j]=mn[i-1][j]+v
            else:
                mx[i][j]=v+max(mx[i-1][j],mx[i][j-1])
                mn[i][j]=v+min(mn[i-1][j],mn[i][j-1])
    return mn[-1][-1], mx[-1][-1]

Задание 2. Подотрезок убывающей последовательности максимальной суммы (выводить целую часть)

Условие: дана последовательность вещественных чисел (в столбце электронной таблицы). Нужно выбрать подряд идущие числа так, чтобы каждое следующее число было меньше предыдущего, и сумма выбранных была максимальна. В ответ — только целая часть максимальной суммы.

Это слайд-шоу требует JavaScript.

DP-идея

Пусть dp[i] — максимальная сумма убывающего подотрезка, оканчивающегося на i. Тогда

dp[i] = a[i] + (dp[i-1] if a[i] < a[i-1] else 0)

Ответ — максимум по dp[i], затем взять целую часть. Граница: dp[0]=a[0].

Задание 3. Ладья 15×15: вправо/вниз на любое число клеток, максимум суммы по остановкам

Условие: в каждой клетке целое число. В левом верхнем углу — ладья. Ходы: на любое число клеток вправо или вниз (влево/вверх нельзя). Надо попасть в правый нижний угол, максимизируя сумму чисел в клетках остановок (включая начальную и конечную).

Это слайд-шоу требует JavaScript.

DP-переход

Пусть best[i][j] — максимум для клетки (i,j) (1..15). Тогда:

best[i][j] = val[i][j] + max( max(best[i][k] for k<j),  max(best[k][j] for k<i) )

То есть можно прийти из любой клетки влево в той же строке или выше в том же столбце (ладья идёт «длинным» ходом). Старт best[1][1]=val[1][1]. Ответ — best[15][15].

Задание 4. Робот 15×15: ходы вправо, вниз, диагональ вправо-вниз, максимум суммы

Условие: робот из левого верхнего в правый нижний, за ход — на одну клетку вправо, вниз или по диагонали вправо-вниз; сумма значений по пути (включая старт и финиш) максимальна.

Это слайд-шоу требует JavaScript.

DP-переход

best[i][j] = val[i][j] + max(best[i-1][j], best[i][j-1], best[i-1][j-1])

Границы: первая строка/столбец считаются из единственных доступных направлений. Ответ — best[15][15].

Задание 5. Робот из левого нижнего в правый верхний: вправо/вверх; в сумму включаются только «улучшающие» клетки

Условие: поле 15×15, старт — левый нижний, финиш — правый верхний. Шаги: на одну клетку вправо или вверх. Ведём сумму по правилу: число включается в сумму, если оно больше числа в предыдущей клетке пути; иначе сумма не меняется. Начальная клетка всегда включается. Максимизировать итоговую сумму.

Это слайд-шоу требует JavaScript.

DP-переход

Храним две величины в клетке: лучший итог и последнее взятое значение. На практике достаточно хранить только лучшую сумму, а сравнение делаем на сопоставлении со значением клетки-предшественника, из которой пришли:

best[i][j] = max(
  best[i][j-1] + (val[i][j] if val[i][j] > val[i][j-1] else 0),
  best[i-1][j] + (val[i][j] if val[i][j] > val[i-1][j] else 0)
)

Старт: нижний левый включается в сумму. Идём «вверх/вправо» по индексам соответствующим координатам. Ответ — в правом верхнем.

Задание 6. Квадрат N×N (1<N<30), стены между клетками: шаги вправо/вниз; максимальная и минимальная суммы монет

Условие: шаги на одну клетку вправо/вниз, внешние стены и внутренние стены между соседними клетками (через стену пройти нельзя). В клетках лежат монеты 1..100, старт/финиш включаются. Найти минимальную и максимальную суммы на маршруте из левого верхнего в правый нижний.

DP-переход с проверкой стен

if no_wall_left_to(i,j):   # можно прийти слева
    max[i][j] = max(max[i][j], val[i][j] + max[i][j-1])
    min[i][j] = min(min[i][j], val[i][j] + min[i][j-1])
if no_wall_top_to(i,j):    # можно прийти сверху
    max[i][j] = max(max[i][j], val[i][j] + max[i-1][j])
    min[i][j] = min(min[i][j], val[i][j] + min[i-1][j])

Недостижимые клетки игнорируем (значения остаются −∞ / +∞). Итог: max[N][N], min[N][N].

Задание 7. Энергия робота с барьерами и зарядками: максимум и минимум энергии на финише

Условие: робот стартует в левом верхнем углу прямоугольного поля, начальный запас энергии — 3000. Разрешённые шаги: на одну клетку вправо/вниз; выход за пределы запрещён. Некоторые клетки окружены границами — в них заходить нельзя. Проходя обычную клетку, робот тратит энергию, равную числу в клетке; в клетках с выделенным фоном — пополняет запас на указанное число (то есть «стоимость» там отрицательная). Нужно найти максимальный и минимальный запас энергии на финише (правый нижний угол).

Это слайд-шоу требует JavaScript.

Нормализация «цен» и DP

Пусть cost[i][j] — потеря энергии на клетке (для зарядной станции она отрицательна: пополнение). Тогда энергетический баланс:

energy[i][j] = start_energy - path_cost[i][j],
где path_cost[i][j] = минимальная (для максимальной энергии) или максимальная (для минимальной энергии) суммарная «стоимость» пути до (i,j).

То есть считаем две таблицы: minCost и maxCost на пути, затем переводим их в энергию на финише: maxEnergy = 3000 - minCost[N][M], minEnergy = 3000 - maxCost[N][M]. Переходы допускаются только если нет стен/запретных клеток.

# Инициализация
best = fill(-INF); best[1][1] = val[1][1]          # максимум
# или
best = fill(+INF); best[1][1] = val[1][1]          # минимум

# Переходы (набор направлений по задаче):
for i in 1..N:
  for j in 1..M:
    for (pi,pj) in предшественники(i,j) допустимые ходом и без стен:
       best[i][j] = op( best[i][j], val[i][j] + best[pi][pj] )
# где op = max или min (по условию),
# предшественники: слева/сверху/диагональ/любая длина по строке/столбцу и т.д.

Итоги и проверочный список

• Точно определите допустимые ходы (шаг на 1, диагональ, «ладья» на любое число клеток).
• Не забудьте про старт/финиш: значения в этих клетках включаются в сумму/баланс.
• Для задач «макс и мин одновременно» считайте две таблицы (или одну с параметром операции).
• При стенах/запретах «отрезайте» переходы — такие рёбра в графе пути не существуют.