Динамика (14 ноября 2017)

  1. bitset: рюкзак за O(nS/w)

  2. НОП: оптимизация памяти
    1. Без восстановления ответа храним только 2 строки
    2. С восстановлением ответа храним только bitset<N> f[N];
    3. Алгоритм Хиршберга

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

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