Divide&Conquer оптимизация

Материал из Algocode wiki
Перейти к: навигация, поиск

Пусть у нас была динамика $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