Задачи на динамику (8 октября 2015)

1. Динамика: общие идеи
1. Калькулятор.Easy: x → x+1, 2x, 3x; n ≤ 10⁶.
2. Калькулятор.Hard: x → 2x, 2x+1, 3x, 3x+1, ; n ≤ 10¹⁸.
3. Динамика вперед, назад, рекурсивно-ленивая (на примере задачи про калькулятор)
4. Динамика и ацикличный граф: состояния, переходы, вперед, назад, ленивая
5. Восстановление ответа: храним ссылки
2. Задачи
1. Количество способов дойти из 1 в N, используя ходы на плюс 1..k
2. Максимальный по сумму чисел лево-верхний путь в матрице c дыркой
3. Задача Иосифа (n людей по кругу, выходит каждый k-й, кто остался?)
4. Есть одна кучка. Двое играют в игру "первый может брать a₁, a₂, ... a_k, второй может брать b₁, ... b_m", кто не может ходить проиграл
5. Рюкзак без стоимостей: решение за O(nW) времени, O(W) памяти, с восстановлением ответа.
6. Рюкзак без стоимостей + bitset, решение за O(nW / wordlen)
7. Выбрать самую длинную подпоследовательность-палиндром O(n²)
8. Наибольшая общая возрастающая подпоследовательность
9. Folding: запаковать строку timus : 1238