$ Динамика
vb = [Ваня]
sk = [Сережа.K]
sm = [Сережа.М]
# $sk$ Динамика: общая мысль и задачи
## Задача про возрастающую подпоследовательность
### Общее состояние процесса "строим слева направо" [i, x, len]
### len[i] → max, x = a[i]
### x[i, len] → min
### x[len] → min (i → i+1 меняем только один x[len])
### i[x, len] → min
### Итого мысль: сперва выписываем все, что имеем, а потом пробуем что-нибудь сделать функцией, что-нибудь состоянием
## Задачи на подмножествах
### Найти гамильтонов путь за O(2^nn^2)
### Найти гамильтонов путь за O(2^nn)
### Для каждого n-элементного множества B узнать, является ли оно подмножеством одного из A_1, A_2, ..., A_m
### Решения за O(2^nm), O(2^nn). ДЗ: можно сделать и за O(2^n)
## Задача про разбиение n компов на прямой на k серверов-отрезков
### Решение с nk состояниями и переходом
### Считаем сумму для одного сервера-отрезка за O(1)
### Считаем p[l, r] для всех l, r − оптимальную позицию сервера на отрезке
### Учимся пересчитывать T[i, j] − начало послднего j-го сервера-отрезка для первых i компов
### T[i+1,j] ≥ T[i,j] ≥ T[i,j-1] ⇒ получаем решение за O(n^2)
## Разбор задачи LCIS (наибольшая общая возрастющая)