Динамика (18 ноября 2019)

  1. bitset
    1. Подробный рассказ bitset: что может, как это делает.
    2. Оптимизируем рюкзак до nS/w
    3. Пояснение про асимптотику: w=64, но также w ≥ logn, значит можно писать под O(...)
    4. Оптимизируем в НОП память до n2/w (восстановление ответа всё ещё доступно).

  2. Напоминание про НОП, повторение Хиршберга
    1. Мы умеем получать O(n) память без восстановления ответа, храня два последних слоя (идея слоёв ещё нужна)
    2. Мы умеем получать O(n) память с восстановлением ответа: алгоритм Хиршберга

  3. НВП (Наибольшая Возрастающая Подпоследовательность) за nlogn
    1. Динамика за O(n2): len[i] → max, конец ровно в i, переход i → j
    2. Общее состояние описанного выше процесса "идём слева направо, берём числа в ответ" : [j, len, last=a[i]] − дошли до j, взяли len чисел, последнее взятое i
    3. Динамика за O(n2): last[j,len] → min. Ход динамики: j↑, слой last[j] → слой last[j+1]
    4. Замечаем свойства массива last[j]: возрастает, отличается от last[j+1] только в одной точке
    5. Оптимизируем до O(nlogn), реализация: for (int x : a) *lower_bound(last,last+n,x) = x

  4. DP − измельчение перехода, выбор состояния, функции (на примере задачи про погрузку корабля)
    1. Условие: есть массив грузов (a[i]), по очереди грузятся корабли (все размера W), корабль = взять что-то слева + взять что-то справа. Погрузить всё мин числом кораблей.
    2. Переинтепретация: идём с двух краёв, набираем рюкзаки, разбить предметы на минимальное число рюкзаков.
    3. Решение #1: O(n4), k[L,R] → min, переход = перебрать префикс и суффикс
    4. Решение #2: O(n3), k[L,R] → min, переход = перебрать только префикс, суффикс вторым указателем
    5. Решение #3: O(n3), w[L,R,k] → min, переход или закончить погрузку, или взять ещё один предмет (сделали измельчение)
    6. Решение #4: O(n2), pair [L,R] → min, переход или закончить погрузку, или взять ещё один предмет (перенесли часть состояния в функцию)
    7. Заметим, что к решению #4 применимы оптимизации по памяти (и "хранить последние две строки" и алгоритм Хиршберга)

  5. (На практику!) Ещё одна история про выбор состояния: рюкзак со стоимостями, веса большие, стоимости маленькие.
− Перерыв −
  1. DP и возведение матрицы в степень
    1. Пути в графе (количество путей длины ровно k)
    2. Числа фибоначчи (начали на практике)
    3. Рекуррентные соотношения за O(k3 log n) (начали на практике)
    4. Реклама: рекуррентные соотношения можно решать и за O(k log k log n)

  2. DP и два указателя (серверы за O(n2)) без док-ва
    1. Постановка задачи: разбить массив длины n на k отрезков
    2. Естественная динамика minCost[k,n], переход − отделить k-й отрезок, внутри перехода ставим оптимальный сервер на отрезок
    3. Постановка оптимального сервера на отрезок − взвешенная медиана. Можно сделать предподсчёт server[l,r]
    4. Также известна стоимость отрезка [l,r], она выражается через частичные суммы весов prefixSum[r+1], prefixSum[l], prefixSum[server[l,r]]
    5. Получили решение за O(n2k).
    6. Оптимизация Кнута: заменим перебор 0 ≤ p[k,n] ≤ n-1 на p[k-1,n] ≤ p[k,n] ≤ p[k,n+1]
    7. Разделяй и властвуй: используем p[k,n] ≤ p[k,n+1], делаем переход p[k] → p[k+1] на отрезке [l,r]: p[k,l] ≤ p[k,i] ≤ p[r,i], посчитаем за O(r-l) p[k,m], сделаем 2 рекурсивных вызова.