Divide&Conquer оптимизация
Пусть у нас была динамика $dp_i = \min_{k=1}^i f(i, k)$, для которой выполнялась монотонность точки перегиба ($opt_{i} \le opt_j$) (а еще $f(i, k)$ не зависела от $dp$). Divide&Conquer оптимизация позволяет посчитать эту динамику за $O(n \log n)$.
Идея
Давайте мы будем считать значения динамики не по порядку, а по принципу "разделяй и властвуй". Сначала посчитаем динамику для средней точки, потом рекурсивно сделаем аналогичное действие для левой и правой частей массива. Пока что это все еще работает за квадратичное время, но посмотрим на происходящий процесс внимательнее. Когда мы считали динамику для отрезка $[l, r]$, мы посчитали $opt_{\frac{l + r}{2}}$. Из монотонности точки перегиба $opt$ для всех элементов на $[l, \frac{l + r}{2}]$ будет не больше $opt_{\frac{l + r}{2}}$, а для $[\frac{l + r}{2}, r]$ — не меньше. Поэтому будем поддерживать в рекурсии "активный" отрезок с теми индексами, которые могут быть точками оптимума для динамики. На каждом уровне рекурсии суммарная длина отрезков будет $O(n)$, поэтому суммарно алгоритм потребует $O(n \log n)$ времени.
Реализация
В слоистой динамике реализация будет выглядеть так:
1 int layer;
2 void calc(int tl, int tr, int l, int r) {
3 if (tl > tr) {
4 return;
5 }
6 int tm = (tl + tr) / 2;
7 int opt = -1;
8 for (int i = l; i <= min(r, tm - 1); i++) {
9 if (dp[tm][layer] > dp[i][layer - 1] + cost(i + 1, tm)) {
10 dp[tm][layer] = dp[i][layer - 1] + cost(i + 1, tm);
11 opt = i;
12 }
13 }
14 calc(tl, tm - 1, l, opt);
15 calc(tm + 1, tr, opt, r);
16 }
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s