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

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