Задачи на динамику (15 октября 2015)

1. Задача take про 2D возрастающую подпоследовательность (из контеста)
1. Решение за O(n³) номер 1: min_end[i, j, length]
2. Решение за O(n³) номер 2: перебираем клетки [i, j] в порядке возрастания a[i, j], и считаем минимум на [0..i] × [0..j] за O(n)
2. LCP[i,j] за O(n²) (наибольший общий префикс i-го и j-го суффиксофф)
3. Задачи на подотрезках
1. Folding за O(n³) timus : 1238
2. Взвешенный бинпоиск за O(n³) (стоимость обращения к элементу i равна cost[i]; минимизируем худший случай при условии, что выбираем произвольный элемент)
3. Покраска забора painter за O(n³k), за O(n³) (дан массив цветов − что должно получиться, один ход − покрасить отрезок, минимизировать число ходов)
4. Динамика по подмножествам
1. Множества, хранение, операции: &, |, ^, (1 << i), (x >> i) & 1
2. Для каждого числа от 0 до (2^k)-1 за O(2^k) посчитать количество бит в нём (размер каждого подмножества)
3. Для каждого числа от 0 до (2^k)-1 за O(2^k) посчитать старший бит в нём
4. Для каждого подмножества множества за O(2^k) посчитать сумму элементов в нём (кодим эту задачу)
5. Для каждого множества вершин в графе за O(2^k) проверить, независимое ли оно
6. Задача о гамильтоновом пути
7. Задача о гамильтоновом цикле
8. Задача коммивояжёра
5. Бонус: динамика по скошенному профилю, рекурсивный вариант на примере "количества покрытий доминошками"