ДП, вторая лекция. 0. Повторение про дп, состояния, etc 1. Bitset, глубже 1.1 Простые операции (|, &, ^), чуть более сложные (<<, >>), O(n/w) 1.2 Почему w >= log(n) 1.3 (*?) НОП и O(n^2/w) памяти. 2. Хиршберг, глубже 2.1 Повтор про метод с предыдущей пары 2.2 Чуть больше о том, как писать 2.3 Второй метод, ручками бьём задачку (на примере НОП) на половинки 2.4 Где применимо: НОП, пути на матрице, стоимостной рюкзак 3. НВП 3.1 Вспоминаем как было за O(n^2) 3.2 Формулируем процесс 3.3 Делаем дп last[i, len] 3.4 Наблюдение last_i[len] строго возрастает 3.5 Делаем переход 3.6 Псевдокод 4. Погрузка кораблей 4.1 За O(n^4) 4.2 За O(n^3) через уменьшение через переходов 4.3 w[i, j, full], хитрая динамика за куб 4.4 ещё хитрее: dp[i,j] = , дп за квадрат 5. Матрицы 5.1 Рекурренты (фибоначчи) 5.2 Пути на графе, простая дп, и через матрицу в степени 6. Почтовые отделения 6.1 Задачка 6.2 cost(l, r) 6.3 Динамика за O(n^2 k) 6.4 Оптимизация кнута: O(n^2) (без доказательства неравенства) 6.5 Оптимизация через D&C: O(nk log(n))