ЛКШ 2018, 9-й день, Оптимизации ДП (Даня Николенко)

Общая задача для следующих пунктов 1, 2, 3, 7: n точек на прямой, разбить на k отрезков, минимизировав сумму квадратов длин.

1. Разделяй и властвуй, O(k * nlogn).
2. Оптимизация Кнута:
   • Решение нашей задачи за O(n²).
   • Точки на окружности, k-угольник макс. площади на этих точках, O(n²logk).
3. Convex hull trick. Бинпоиск: O(k * nlogn), указатель: O(k * n).
4. Правильный выбор состояния. Задача о кораблях.
5. ДП по подмаскам:
   • Гамильтонов путь за O(2ⁿ * n) битовым сжатием.
   • Сумма элементов для каждого подмножества, O(2ⁿ).
6. Префиксные суммы:
   • Префиксные суммы на прямоугольнике без включений-исключений.
   • Сумма по подмаскам, O(2ⁿ * n).
   • Обратная задача к предыдущей: повторяем действия в обратном порядке.
7. Лямбда оптимизация.
8. [дополнительно] Рюкзак:
   • Рюкзак на отрезке.
   • Битовое сжатие: O(S * n / bitset).
   • Корневая #1: O(sqrt(S)) различных весов, O(S * sqrt(S)).
   • Корневая #2: сводим n предметов к O(sqrt(S)) предметов ==> применяем битовое сжатие и получаем O(S * sqrt(S) / bitset).