Занятие 2. Параллель A — Оптимизации DP

1. Переливайка (small-to-large) 0:09:00

Дано дерево; для каждой вершины нужно посчитать ДП, размер которой не превосходит размера поддерева. Суммарный размер всех ДП — $O(n^2)$, но есть способ сделать $O(n \log n)$.

Идея. Сначала запускаемся от самого большого сына («тяжёлого») и крадём его ДП (не копируем, а просто «забираем себе», например, через swap). Затем к своей ДП приливаем ДП остальных детей.

Классический пример — количество различных цветов в поддереве каждой вершины. В каждой вершине храним set цветов:

vector<set<int>> colors(n);

void dfs(int v, int p) {
    int heavy = -1;
    for (int u : g[v]) if (u != p)
        if (heavy == -1 || colors[u].size() > colors[heavy].size()) heavy = u;
    for (int u : g[v]) if (u != p && u != heavy) dfs(u, v);
    if (heavy != -1) {
        dfs(heavy, v);
        swap(colors[v], colors[heavy]);   // крадём сет тяжёлого сына
    }
    colors[v].insert(color[v]);
    for (int u : g[v]) if (u != p && u != heavy)
        for (int c : colors[u]) colors[v].insert(c);
    ans[v] = colors[v].size();
}

2. Рюкзак на дереве за $O(n^2)$ 0:25:00

Задача. Посчитать число независимых множеств размера $k$ для всех $k$ в дереве. Наивный рюкзак по сыновьям даёт $O(n^2)$ (а не $O(n^3)$).

ДП: $dp[v][k][t]$ — число независимых множеств размера $k$ в поддереве $v$, где $t \in \{0,1\}$ — взяли ли саму вершину $v$. При слиянии двух ДП размеров $x$ и $y$ перебираем пары — это $O(xy)$.

Ограничение до $k$. Если нам нужны только размеры $\le k$, ДП в каждой вершине имеет размер $\le \min(k, \text{размер поддерева})$ — суммарно получается $O(nk)$.

3. Convex Hull Trick (CHT) 0:35:00

Задача. Есть прямоугольники (каждый задан шириной и высотой). Нужно выбрать подмножество, максимизирующее сумму площадей минус сумму стоимостей.

Отсортируем по ширине $x$. Ключевое свойство: в оптимальном ответе высоты выбранных прямоугольников убывают (иначе внутренний прямоугольник не даёт вклада в площадь, но за него платим). ДП:

Внутренний максимум — это максимум прямых $k_j x + b_j$, где $k_j = -x_j$, $b_j = dp[j]$, вычисленных в точке $x = y_i$. Прямые добавляются с убывающими наклонами (так как $x_j$ возрастают).

Структура. Поддерживаем стек прямых, образующих верхнюю огибающую, вместе с координатами точек пересечения. При добавлении новой прямой:

// прямые y = k*x + b, добавляются с убывающими k; ищем максимум
vector<Line> hull;      // стек прямых
vector<long double> pt; // pt[i] — правая граница отрезка, где i-я прямая лучшая; pt[0] = +INF, дальше убывают

void add(Line l) {
    while (!hull.empty()) {
        long double x = intersect(l, hull.back());   // левее x прямая l выше последней
        if (x >= pt.back()) {                        // последняя прямая нигде не лучшая
            hull.pop_back();
            pt.pop_back();
        } else break;
    }
    pt.push_back(hull.empty() ? INF : intersect(l, hull.back()));
    hull.push_back(l);
}
long long query(long long x) {
    // последняя i с pt[i] >= x (pt убывает, поэтому такие i образуют префикс)
    int id = partition_point(pt.begin(), pt.end(), [&](long double v) { return v >= x; }) - pt.begin() - 1;
    return hull[id].k * x + hull[id].b;
}

Запрос — бинпоиск по точкам пересечения ($O(\log n)$). У верхней огибающей с убывающими наклонами новая прямая выигрывает левее, поэтому точки пересечения в стеке убывают. (Для минимума при убывающих наклонах точки, наоборот, возрастают, и подойдёт обычный upper_bound.) Если и запросы по $x$ монотонны, можно поддерживать указатель на последнюю оптимальную прямую и двигать его вперёд — запросы за $O(1)$ амортизированно.

4. Лямбда-оптимизация (Aliens trick) 1:06:00

Задача. Разбить $n$ точек на $k$ отрезков, минимизировав сумму квадратов длин отрезков.

Исходная ДП $dp[i][k]$ за $O(n^2k)$. Идея: добавим штраф $\lambda$ за каждый отрезок и будем решать задачу без ограничения на число отрезков (просто минимизируем $\sum \text{квадрат} + \lambda \cdot (\text{число отрезков})$). Это одномерная ДП, решаемая CHT за $O(n \log n)$.

Функция $f(k)$ выпукла (это ключевое условие). Тогда $cost_\lambda$ — нижняя огибающая семейства прямых $f(k) + \lambda k$. Бинпоиском по $\lambda$ подбираем такое значение, при котором оптимальное число отрезков равно $k$, и восстанавливаем $f(k) = cost_\lambda - \lambda k$.

5. Оптимизация Кнута 1:34:00

Задача. Разбить массив на $k$ отрезков, минимизируя сумму квадратов сумм элементов на отрезках.

Пусть $opt[i][j]$ — оптимальное место разреза для $dp[i][j]$ (разбиение первых $i$ элементов на $j$ отрезков). Ключевое свойство:

Поэтому, считая ДП в правильном порядке ($j$ по возрастанию, $i$ по убыванию), для каждого состояния перебираем $k$ только в границах $[opt[i][j-1],\ opt[i+1][j]]$. Суммарная работа по каждой диагонали $O(n)$, а диагоналей $O(n)$ — итого $O(n^2)$.

6. Разделяй и властвуй + мин-плюс свёртка 1:47:00

Разделяй и властвуй для ДП

Та же задача (разбиение точек на $k$ отрезков). Считаем ДП по слоям (по числу отрезков). Внутри слоя выполняется пересчёт с монотонными оптимумами: если $i$ растёт, то оптимальный разрез тоже не убывает.

Пишем рекурсивную функцию, которая знает, что оптимумы для всех $i$ на отрезке $[l, r]$ лежат в $[optL, optR]$:

// считаем dp[][cur] по dp[][prev]; оптимумы монотонны
void solve(int l, int r, int optL, int optR) {
    if (l > r) return;
    int m = (l + r) / 2, opt = -1;
    dp[m] = INF;
    for (int k = optL; k <= min(optR, m - 1); ++k) {
        long long cur = prev[k] + cost(k + 1, m);
        if (cur < dp[m]) { dp[m] = cur; opt = k; }
    }
    solve(l, m - 1, optL, opt);
    solve(m + 1, r, opt, optR);
}

Суммарная длина отрезков $[optL, optR]$ на каждом уровне рекурсии $O(n)$, уровней $\log n$ — итого $O(n \log n)$ на слой, всего $O(nk \log n)$.

Мин-плюс свёртка 1:55:00

Даны массивы $a$ и $b$; нужно посчитать $c_i = \min_{x+y=i} (a_x + b_y)$. Для произвольных массивов быстрее $O(n^2)$ не известно. Но если $a$ выпуклый, то оптимумы монотонны и работает та же разделяйка — $O(n \log n)$ (а специальными алгоритмами даже $O(n)$).

7. Оффлайн-связность и очередь из роллбека 2:05:00

Задача. Дан массив рёбер; для каждого запроса $[l, r]$ проверить, связен ли граф из рёбер отрезка.

Зафиксировав левую границу $l$, по правой есть монотонность: начиная с некоторого $r$ граф связен, и эта граница не убывает с ростом $l$. Значит, можно применить разделяйку с ДСУ с откатами (rollback DSU).

Поддерживаем ДСУ, которая умеет добавлять ребро и откатывать последнее добавление (храня стек изменений). В разделяйке для центральной левой границы добавляем рёбра, пока граф не станет связным; для рекурсивных вызовов аккуратно откатываем/накатываем нужные рёбра.