Продвинутое динамическое программирование
Классические ДП: рюкзак 0/1 за O(n·W) и наибольшая возрастающая подпоследовательность за O(n log n).
Уровень выше — ДП с двумя параметрами и ДП с оптимизациями. Разберём две задачи, которые обязан знать каждый олимпиадник.
Рюкзак 0/1: n предметов с весом и ценностью, рюкзак вместимостью W; каждый предмет берётся один раз; максимизировать ценность.
Состояние: dp[cap] — максимальная ценность при вместимости cap. Для каждого предмета обновляем dp: либо не берём (ничего не меняется), либо берём — тогда dp[cap] = dp[cap - w] + cost.
Тонкость, ради которой задачу и разбирают: внутренний цикл по вместимости идёт СВЕРХУ ВНИЗ. Иначе предмет успеет «положиться» дважды в одном проходе.
Рюкзак 0/1. Введите: 4 8, затем пары «вес ценность»: 3 4, 4 5, 5 6, 2 3
Ответ на примере: 10 (предметы весом 3 и 5: ценности 4 + 6). Сложность O(n·W) — обратите внимание: она зависит от ЧИСЛЕННОГО значения вместимости, поэтому рюкзак хорош при W до миллионов, но бессилен при W = 10¹⁸.
Вторая классика — наибольшая возрастающая подпоследовательность (LIS). Наивное ДП за O(n²) все знают; олимпиадная версия — O(n log n): держим массив tail, где tail[k] — минимально возможный конец возрастающей подпоследовательности длины k+1. Каждый новый элемент либо продлевает лучшую подпоследовательность, либо улучшает чей-то конец — позиция ищется бинарным поиском.
LIS за O(n log n). Введите: 8, затем 10 9 2 5 3 7 101 18
Ответ на примере: 4 (например, 2 3 7 18). Важно понимать: tail — НЕ сама подпоследовательность, а только «лучшие концы»; но её длина всегда равна длине LIS.
Как придумывать состояния ДП: спросите себя, какой МИНИМУМ информации о префиксе решения достаточно, чтобы продолжать оптимально. Это и есть параметры состояния.
Задание: выведите не длину LIS, а саму подпоследовательность (храните для каждого элемента, кого он продлил).
Отметьте урок пройденным.