Динамика (20 ноября 2014)
- Динамика: общие идеи
- Динамика вперед, назад, рекурсивно-ленивая (на примере задачи про калькулятор) [code]
- Динамика и ацикличный граф: состояния, переходы, вперед, назад, ленивая
- Ленивая динамика − тоже самое, что и dfs [code]
- Рюкзак. Только веса, ценностей нет
- Решение за O(nW) [code]
- Использование O(W) памяти с восстановлением ответа [code]
- Использование bitset, решение за O(nW/s), где s − длина машинного слова [code]
- Примеры задач
- Наибольшая общая подпоследовательность двух, трех (делаем память линейной, квадратной) [code]
- Найти кратчайший путь/количество путей коня, который ходит только вправо
- LCP (largest common prefix) за O(n2) [code]
- Нужно упаковать строку: задача folding, динамика на подотрезках [code] [example]
- Нужно упаковать строку: LZSS (разбиралась на доске)
- Битовые операции
- Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов [code]
- Пересечение, объединение, разность. Проверка, содержится ли [code]
- Младший бит [code]
- Старший бит [code]
- Динамика по подмножествам
- Сумма на подмножестве, количество бит в числе, старший бит [code]
- Гамильтонов путь за O(2nn2) времени, за O(2nn) времени [code]
- Гамильтонов путь за O(2nn) времени [code]
- Для каждого множества проверить, независимое ли оно [code]
- Перебор всех подмножеств, надмножеств. Раскраска графа в минимальное количество цветов за O(3n) [code]
- Решение мультирюкзака (унести все вещи минимальным числом подходов) за O(3n).