Динамика (20 ноября 2014)

  1. Динамика: общие идеи
    1. Динамика вперед, назад, рекурсивно-ленивая (на примере задачи про калькулятор) [code]
    2. Динамика и ацикличный граф: состояния, переходы, вперед, назад, ленивая
    3. Ленивая динамика − тоже самое, что и dfs [code]
    4. Рюкзак. Только веса, ценностей нет
      1. Решение за O(nW) [code]
      2. Использование O(W) памяти с восстановлением ответа [code]
      3. Использование bitset, решение за O(nW/s), где s − длина машинного слова [code]
  2. Примеры задач
    1. Наибольшая общая подпоследовательность двух, трех (делаем память линейной, квадратной) [code]
    2. Найти кратчайший путь/количество путей коня, который ходит только вправо
    3. LCP (largest common prefix) за O(n2) [code]
    4. Нужно упаковать строку: задача folding, динамика на подотрезках [code] [example]
    5. Нужно упаковать строку: LZSS (разбиралась на доске)
  3. Битовые операции
    1. Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов [code]
    2. Пересечение, объединение, разность. Проверка, содержится ли [code]
    3. Младший бит [code]
    4. Старший бит [code]
  4. Динамика по подмножествам
    1. Сумма на подмножестве, количество бит в числе, старший бит [code]
    2. Гамильтонов путь за O(2nn2) времени, за O(2nn) времени [code]
    3. Гамильтонов путь за O(2nn) времени [code]
    4. Для каждого множества проверить, независимое ли оно [code]
    5. Перебор всех подмножеств, надмножеств. Раскраска графа в минимальное количество цветов за O(3n) [code]
    6. Решение мультирюкзака (унести все вещи минимальным числом подходов) за O(3n).