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

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

1. Разделяй и властвуй, O(k*nlogn).
2. Оптимизация Кнута:
   - Решение нашей задачи за O(n2).
   - Точки на окружности, k-угольник макс. площади на этих точках, O(n2logk).
3. Convex hull trick. Бинпоиск: O(k*nlogn), указатель: O(k*n).
4. Правильный выбор состояния. Задача о кораблях.
5. ДП по подмаскам:
   - Гамильтонов путь за O(2n*n) битовым сжатием.
   - Сумма элементов для каждого подмножества, O(2n).
6. Префиксные суммы:
   - Префиксные суммы на прямоугольнике без включений-исключений.
   - Сумма по подмаскам, O(2n*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).