Динамика (27 февраля 2014)

  1. Задачи
    1. Наибольшая общая двух за O(n2)
    2. Наибольшая общая трех за O(n3)
    3. Наибольшая общая возрастающая за O(n3), O(n2)
  2. Пример: наибольшая общая подпоследовательность
  3. Способы реализовать динамику
    1. Вперед [code]
    2. Назад [code-1] [code-2]
    3. Лениво (рекурсивно) [code]
    4. Случай когда ленивость улучшает: минимальное по весу паросочетание [text]
  4. Восстановление ответа
    1. Храним весь ответ [code]
    2. Храним ссылку назад [code] [bits]
    3. Ничего не храним [code]
  5. Оптимизация по памяти
    1. Храним только две строки, копируем [code]
    2. А теперь не копируем [code]
    3. А теперь все по модулю два [code]
  6. Рекурсия и доминошки
    1. Рекурсия [code]
    2. Запоминание, изломанный профиль [code]
  7. Интересные приемы
    1. Задача о возрастающей подпоследовательности
      1. len[i]
      2. len[i,j], x=a[j]
      3. [i, x, len]
      4. x[i, len], xi → xi+1
    2. Задача про погрузку грузов (можно брать вещи с двух концов последовательности, в ящик помещается W, минимизировать кол-во ящиков)
      1. 2 3 4 5 6 7, W = 9 : 2+3+5 = Wrong Way, 2+7, 3+6, 4+5 = 3 ящика
      2. Решение за O(n5) k[L, R] → [a, b]
      3. Решение за O(n3) k[L, R] → [a, b], где b = min возможный
      4. Решение за O(n2) [a, b, k, w] : pair(k, w) [a, b]
      5. Оптимизация памяти до линии