Оптимизация через разделяй-и-властвуй

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

Посмотрим на формулу пересчета динамики из базового решения:

Обозначим за $opt[i, j]$ оптимальный $k$ для данного состояния — то есть аргминимум от выражения выше. Для однозначности, если оптимальный индекс не один, то выберем среди них самый правый.

Конкретно в задаче покрытия точек отрезками можно заметить следующее:

Интуация такая: если нам нужно покрыть больший префикс точек, то начало последнего отрезка точно не будет раньше.

#Алгоритм

Пусть мы уже знаем $opt[l, k]$ и $opt[r, k]$ и хотим посчитать $opt[i, k]$ для какого-то $i$ между $l$ и $r$. Тогда, воспользовавшись неравенством выше, мы можем сузить отрезок поиска оптимального индекса для $i$ со всего отрезка $[0, i - 1]$ до $[opt[l, k], opt[r, k]]$.

Будем делать следующее: заведем рекурсивную функцию, которая считает динамики для отрезка $[l, r]$ на $k$-том слое, зная, что их $opt$ лежат между $l’$ и $r’$. Эта функция просто берет середину отрезка $[l, r]$ и линейным проходом считает ответ для неё, а затем рекурсивно запускается от половин, передавая в качестве границ $[l’, opt]$ и $[opt, r’]$ соответственно:

// [ l,  r] -- какие динамики на k-том слое посчитать
// [_l, _r] -- где могут быть их ответы
void solve(int l, int r, int _l, int _r, int k) {
    if (l > r)
        return; // отрезок пустой -- выходим
    int opt = _l, t = (l + r) / 2;
    // считаем ответ для f[t][k]
    for (int i = _l; i <= min(_r, t); i++) { 
        int val = f[i + 1][k - 1] + cost(i, t - 1);
        if (val < f[t][k])
            f[t][k] = val, opt = i;
    }
    solve(l,     t - 1, _l,  opt, k);
    solve(t + 1, r,     opt, _r,  k);
}

Затем последовательно вызовем эту функцию для каждого слоя:

for (int k = 1; k <= m; k++)
    solve(0, n - 1, 0, n - 1, k);

Так как отрезок $[l, r]$ на каждом вызове уменьшается примерно в два раза, глубина рекурсии будет $O(\log n)$. Так как отрезки поиска для всех элементов на одном «уровне» могут пересекаться разве что только по границам, то суммарно на каждом уровне поиск проверит $O(n)$ различных индексов. Соответственно, пересчет всего слоя займет $O(n \log n)$ операций вместо $O(n^2)$ в базовом решении.

Таким образом, мы улучшили асимптотику до $O(n \cdot m \cdot \log n)$.