Дискретный метод Лагранжа

Эта статья — одна из серии. Рекомендуется сначала прочитать все предыдущие.

В качестве финальной оптимизации мы рассмотрим метод, вдохновленный методом множителей Лагранжа, также в олимпиадной среде называемый «лямбда-оптимизацией».

#Модификация задачи

Рассмотрим немного измененную версию исходной задачи. Пусть нам нужно покрыть те же точки, но теперь нас не ограничивают жёстко в количестве отрезков, а просто штрафуют на какую-то константу $\lambda$ за использование каждого дополнительного отрезка.

Нашу оптимизируемую функцию $g$ тогда можно выразить через $f$ следующим образом:

Эту динамику можно посчитать за $O(n)$: мы ровно это и делали в прошлой статье про Convex Hull Trick.

#Идея

Наблюдение 1. Если в оптимальном решении для $g_i$ мы для какого-то $\lambda$ использовали ровно $k$ отрезков, то это же решение будет оптимальным и для $f[i, k]$.

Наблюдение 2. Если уменьшать $\lambda$, то оптимальное количество отрезков для $g_i$ будет увеличиваться.

Основная идея оптимизации: сделаем бинпоиск по $\lambda$, внутри которого будем находить оптимальное решение для $g_i$ с заданным $\lambda$. Если оптимальное $k^\star$ получилось больше $k$, то следующая $\lambda$ должна быть меньше, а в противном случае наоборот. Когда $k^\star$ совпадёт с $k$, просто выведем чистую стоимость получившегося решения без штрафов.

Таким образом, задача решается за $O(n \log n + n \log m)$, если сортировку точек для CHT делать заранее, а не внутри бинпоиска.

#Реализация

pair<ll, int> dp[maxn]; // dp[i] - (ответ, число отрезков)

void init() {
    for (int i = 0; i < maxn; i++) {
        dp[i] = make_pair(inf, 0);
    }
}

pair<ll, int> check(ll x) { // это можно соптимизировать
    init();
    dp[0] = make_pair(0ll, 0); // 1-индексация
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], {dp[j].first + cost[j + 1][i] + x, dp[j].second + 1});
        }
    }
    return dp[n];
}

ll solve() {
    ll l = -1e14; // границы надо подбирать очень аккуратно!
    ll r = 1;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        pair<ll, int> x = check(mid);
        if (x.second >= k)
            l = mid;
        else
            r = mid;
    }
    pair<ll, int> result = check(l);
    return result.first - l * return.second; // вычитаем штрафы
}

Автор извиняется за качество реализации и призывать читателя её переписать и закомитить.

#Существование решения

Мы пропустили один нюанс: почему вообще существует такая $\lambda$, что оптимальное $k^\star = k$?

В общем случае возможно, что функция $k^\star(\lambda)$ через него «перескакивает», и это действительно проблема: одной лишь монотонности не достаточно, чтобы решать подобным образом произвольные задачи с ограничением на число объектов.

Но в нашей задаче можно заметить следующее: функция $f[i, j]$ нестрого вогнутая (выпуклая вверх) по своему второму аргументу, то есть

Иными словами, дополнительная «выгода» от добавления каждого следующего отрезка не увеличивается.

Теперь, на выражение для модифицированной динамики

можно смотреть как на минимизацию скалярного произведение точек $(f[i, k], k)$ и вектора $(1, \lambda)$.

Так как верхняя огибающая точек $(f[i, k], k)$ выпукла, для каждой точки будет существовать $\lambda$, которая упирается в него, и следовательно $k^\star = k$ гарантированно найдется.