На эту неделю подготовили тренировочный контест по динамике на отрезках.

Это подборка для тех, кто уже знаком с базовой динамикой и хочет перейти к одному из самых важных соревновательных паттернов: dp[l][r], где состояние описывает ответ на отрезке массива, строки, последовательности или выражения.

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

Паттерн A. «Склейка»: перебор точки разреза k

В этих задачах мы обычно считаем dp[l][r] и перебираем точку k, в которой отрезок разбивается на две части. Такой подход часто встречается в задачах на объединение объектов, перемножение матриц, триангуляцию и похожие процессы.

• Склейка камней — https://judje.olprog.ru/problem/stonemergecost
• Перемножение цепочки матриц — https://judje.olprog.ru/problem/matrixchainmult
• Склейка камней по кругу — https://judje.olprog.ru/problem/circularstonemerge
• Минимальная триангуляция многоугольника — https://judje.olprog.ru/problem/minpolygontriangulat
• Склейка камней по K — https://judje.olprog.ru/problem/mergekstones

Паттерн B. «Снимаем края»

Здесь состояние dp[l][r] часто зависит от символов или элементов на концах отрезка. Мы сравниваем левый и правый край, решаем, можно ли их объединить, удалить вместе или нужно обработать один из краёв отдельно.

• Длиннейшая палиндромная подпоследовательность — https://judje.olprog.ru/problem/longestpalindromicsu
• Минимум вставок до палиндрома — https://judje.olprog.ru/problem/mininsertionspalindr
• Минимум разрезов на палиндромы — https://judje.olprog.ru/problem/palindromemincuts
• Стирание палиндромов — https://judje.olprog.ru/problem/palindromeremovalste

Паттерн C. «Игры на отрезке»

В играх на отрезке игроки обычно берут элементы с одного или двух концов. Здесь важно учитывать оптимальную игру соперника: состояние может хранить максимальную выгоду, разность очков или факт победы.

• Берём монеты с концов — https://judje.olprog.ru/problem/pickcoinsfromends
• Игра на концах: кто победит — https://judje.olprog.ru/problem/endpointsgamewinner
• Игра в камни: взять один или два — https://judje.olprog.ru/problem/stonegametakeonetwo

Паттерн D. «Последний ход» и счёт способов

В этих задачах полезно думать не только о том, как начать процесс, но и о том, какой ход был последним. Такой взгляд помогает решать задачи на скобочные выражения, лопание шариков, печать строк и удаление фрагментов.

• Лопаем шарики — https://judje.olprog.ru/problem/burstballoonscoins
• Странный принтер — https://judje.olprog.ru/problem/strangeprinter
• Расстановка скобок для True — https://judje.olprog.ru/problem/booleanparenthesizat
• Минимальное очищение ряда — https://judje.olprog.ru/problem/mininsertclearrow

Этот контест подойдёт тем, кто хочет:

• разобраться с динамикой на отрезках;
• научиться формулировать состояния вида dp[l][r];
• потренировать перебор точки разреза;
• понять, как работают задачи на палиндромы и удаление отрезков;
• освоить базовые игровые динамики;
• увидеть, как идея «последнего хода» помогает строить переходы.

Во время решения полезно каждый раз отдельно проговаривать:

• что означает dp[l][r];
• какие меньшие отрезки нужны для перехода;
• перебирается ли точка разреза k;
• зависят ли переходы от левого и правого края;
• есть ли в задаче игроки и оптимальная стратегия соперника;
• можно ли думать о последнем действии, а не о первом.

Рекомендуем решать подборку по разделам. Сначала пройти задачи на склейку, потому что они хорошо показывают классический переход через k. Затем перейти к палиндромам и снятию краёв, после этого — к играм, а в конце оставить задачи на последний ход и счёт способов.

Такие задачи редко решаются одной готовой формулой. Главное — научиться правильно выбирать смысл состояния и аккуратно строить переходы между меньшими отрезками.

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.