Динамика

  1. [Сережа.K] Динамика: общая мысль и задачи
    1. Задача про возрастающую подпоследовательность
      1. Общее состояние процесса "строим слева направо" [i, x, len]
      2. len[i] → max, x = a[i]
      3. x[i, len] → min
      4. x[len] → min (i → i+1 меняем только один x[len])
      5. i[x, len] → min
      6. Итого мысль: сперва выписываем все, что имеем, а потом пробуем что-нибудь сделать функцией, что-нибудь состоянием
    2. Задачи на подмножествах
      1. Найти гамильтонов путь за O(2nn2)
      2. Найти гамильтонов путь за O(2nn)
      3. Для каждого n-элементного множества B узнать, является ли оно подмножеством одного из A1, A2, ..., Am
      4. Решения за O(2nm), O(2nn). ДЗ: можно сделать и за O(2n)
    3. Задача про разбиение n компов на прямой на k серверов-отрезков
      1. Решение с nk состояниями и переходом
      2. Считаем сумму для одного сервера-отрезка за O(1)
      3. Считаем p[l, r] для всех l, r − оптимальную позицию сервера на отрезке
      4. Учимся пересчитывать T[i, j] − начало послднего j-го сервера-отрезка для первых i компов
      5. T[i+1,j] ≥ T[i,j] ≥ T[i,j-1] ⇒ получаем решение за O(n2)
    4. Разбор задачи LCIS (наибольшая общая возрастющая)