Динамика (19 ноября 2024)

  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(n)
    2. Динамика за O(n2): len[i] → max, конец ровно в i, переход i → j
    3. nlogn: minEnd[len]
    4. Код O(nlogn): for (int x : a) *lower_bound(last, last + n, x) = x
    5. Восстановление ответа

  4. (новое) DP − измельчение перехода, выбор состояния, функции (на примере задачи про погрузку корабля)
    1. Условие: есть массив грузов (a[i]), по очереди грузятся корабли (все размера W), корабль = взять что-то слева + взять что-то справа. Погрузить всё мин числом кораблей.
    2. Переинтепретация: идём с двух краёв, набираем рюкзаки, разбить предметы на минимальное число рюкзаков.
    3. [skipped] Решение #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 рекурсивных вызова.