Динамика по подмножествам, по профилю (30 ноября 2016)

1. Динамика по подотрезкам
1. Сводим задачу к меньшим такого же вида
2. Динамика тоже описывается графом, но не является напрямую задачей поиска пути на этом графе


2. Задача: покрасить вершины графа в минимальное число цветов
1. Предподсчет good[A] за O(2ⁿn²). Решение за O(4ⁿ).
2. Перебор всех надмножеств всех множеств за O(3ⁿ)
3. Перебор всех подмножеств всех множеств за O(3ⁿ)
4. [на практику] замена O(2ⁿn²) на O(2ⁿ) (good[] - динамика).
5. Алгоритм перебора всех максимальных по включению за 3^n/3 = 1.44ⁿ
6. Покраска вершин, описание решения за O(2.44ⁿ).


3. Задачи на подмножествах
1. Рюкзак (Set Cover: покрыть множество {0,1,...,n-1} минимальным числом множеств из набора A₁,...,A_m
2. Перевёрнутая битовая запись числа

1. Meet-In-The-Middle
1. Решение задачи о рюкзаке за 2^n/2n
2. Решение задачи о поиске максимальной клики за 2^n/2
3. Хиршберг − тоже Meet-In-The-Middle
2. DP и скошенный профиль через рекурсию (задача про доминошки)
1. Перебор за O(2^wh/2)
2. Запоминание → получили динамику → доказали число состояний O(2^min(w,h)wh)
3. Как кодировать матрицу? Матрица → одномерный массив → число → хеш