Динамика (9 ноября 2016)

  1. Динамика, вводная (на примерах)
    1. Кратчайшая последовательность операций из 1 получить N, операции: x → x+1,x+7,2x,3x
    2. Вперед
    3. Назад
    4. Рекурсивно-ленивая
    5. Задача про путь "на матрице с дыркам": sum → max кол-во способов
    6. Задача про путь "на матрице с дыркам": можно хранить путь до состояния, можно от состояния
    7. Восстановление ответа, 2 способа: или храним ссылки между состояниями, или не храним
    8. Граф динамики: состояния, переходы, вперед (исходящие рёбра), назад (входящие рёбра), ленивая (только достижимые состояния)
    9. Что нужно, чтобы решить задачу динамикой? Список: состояние динамики, переходы между состояниями, начальное состояние, конечное состояние, порядок пересчёта.
− Перерыв −
  1. Рюкзак
    1. Условие: даны вещи, у них есть веса, выбрать подмножества суммарного веса ровно W
    2. is[i, w i] (w − вес, i − префикс)
    3. is[w] (хранить только последнюю строку)
    4. bitset<W> реализация на bitset-ах
    5. last[w], восстановление ответа с линейной памятью

  2. НОП
    1. Условие: даны две последовательности, выбрать наибольшую общую подпоследовательность
    2. Решение: f[i, j] − длина НОП для s[:i], t[:j]
    3. НВП за n2
    4. Расстояние Левинштейна за n2

  3. НОП: оптимизация памяти
    1. Оптимизация памяти: без восстановления ответа храним только 2 строки
    2. Оптимизация памяти: с восстановлением ответа храним только bitset<N> f[N];
    3. Оптимизация памяти: алгоритм Хиршберга
    4. Область применения хиршберга: расстояние Левинштейна, любая задача монотонная по обеим координатам