Изменения
→Пример задачи, решаемой методом convex hull trick
==Пример задачи, решаемой методом convex hull trick==
Рассмотрим задачу на ДП:
==Наивное решение==
Сначала заметим важный факт : т.к. <tex>c[i] </tex> убывают(нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i] </tex> неотрицательны.Понятно, что нужно затратив минимальную стоимость срубить последнее (<mathtex>n</mathtex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <mathtex>c[n] = 0</mathtex>). Посчитаем следующую динамику : <mathtex>dp[i]</mathtex> {{--- }} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <mathtex>i.</mathtex> будет срублено. База динамики : <mathtex>dp[1] = 0</mathtex>, т.к. изначально пила заправлена и высота первого дерева равна <math>1</math>, по условию задачи.Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадных алгоритмновалгоритмов]], чем к теме данной статьи). Поэтому перед <mathtex>i</mathtex>-м деревом мы обязательно срубили какое-то <mathtex>j</mathtex>-е, причем <mathtex>j < \leqslant i- 1</mathtex>. Поэтому чтобы найти <mathtex>dp[i]</mathtex> нужно перебрать все <mathtex>1 <= \leqslant j < \leqslant i- 1</mathtex> и попытаться использовать ответ для дерева намер номер <mathtex>j</mathtex>. Итак, пусть перед <mathtex>i</mathtex>-м деревом мы полностью срубили <mathtex>j</mathtex>-е, причем высота <mathtex>i</mathtex>-го дерева составляет <mathtex>a[i]</mathtex>, а т.к. последнее дерево, которое мы срубили , имеет индекс <mathtex>j</mathtex>, то стоимость каждого метра <mathtex>i</mathtex>-го дерева составит <mathtex>c[j]</mathtex>. Поэтому на сруб <mathtex>i</mathtex>-го дерева мы потратим <mathtex>a[i] * \cdot c[j]</mathtex> монет. Также не стоит забывать, что ситуацию, когда <mathtex>j</mathtex>-е дерево полностью срублено, мы получили не бесплатно, а за <mathtex>dp[j]</mathtex> монет.Итогвая Итоговая формула пересчета : <mathtex>dp[i] = min_\min\limits_{j=01...i-1}(dp[j] + a[i] * \cdot c[j])</mathtex>.
Посмотрим на код выше описанного вышеописанного решения: '''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n]) dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex> '''for'' ' i = 2 = 1..n-1 { dp[i] = +<tex>+\infty</tex> '''for''' j = 01..i-1 { '''if''' (dp[j] + a[i] * <tex>\cdot</tex> c[j] < dp[i]) dp[i] = dp[j] + a[i] * <tex>\cdot</tex> c[j] } } '''return''' dp[n]Нетрудно видеть, что такая динамика работает за <mathtex>O(n^2)</mathtex>.
==Ключевая идея оптимизации==
[[Файл:picture1convexhull.png]]
==Для чего нужна нижняя ошибающая Цель нижней огибающей множества прямых== Пусть мы считаем динамику для <mathtex>i</mathtex>-го дерева. Его задает <mathtex>x[i]</mathtex>. Итак, нам нужно для данного <mathtex>x[i]</mathtex> найти <mathtex>min_\min\limits_{j=0..i-1}(k[j]*\cdot x[i] + b[ij]) = min_\min\limits_{j=0..i-1}(y[j](x[i]))</mathtex>. Это выражение есть <math>convex(x[i])</math>. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты координатам x следует то, что отрезок, который пересекает прямую <mathtex>x = x[i]</mathtex>, можно найти [[Целочисленный_двоичный_поиск|бинарным поиском]]. Это потребует <mathtex>O(logn\log(n))</mathtex> времени на поиск такого <tex>j</tex>, что <tex>dp[i] = k[j] * \cdot x[i] + b[j]</tex>. Теперь осталось научиться поддерживать множество прямых и быстро добавлять <mathtex>i</mathtex>-ю прямую после того, как мы посчитали <mathtex>b[i] = dp[i]</mathtex>.
==Детали реализации:==
==Реализация==
'''voidint''' Convex-hull-trick<tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n]) st[1] = 1 from front[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font> sz = 1 <font color=green>// текущий размер выпуклой оболочки </font> pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] >= \geqslant front[st[j]] </font > '''for''' i = 2..n { '''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font > pos = pos + 1 j = st[pos] dp[i] = K[j] * <math>\cdot</math> a[i] + B[j] '''if''' (i < n) { <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font > K[i] = c[i] <font color=green>// наши переобозначения переменных </font > B[i] = dp[i] <font color=green>// наши переобозначения переменных </font > x = -<tex>\infty</tex> '''while''' (''true) {'' j = st[sz] x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font > '''if''' (x > from[sz]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font > sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font > } st[sz + 1] = i from front[sz + 1] = x <font color=green>// добавили новую прямую </font > sz = sz + 1 } } '''return''' dp[n] (Здесь функция <tex>\mathtt{divide(a, b) }</tex> возвращает нужное(*) округление <tex>\frac{a }{b}</ tex>. Приведем её код : '''int''' <tex>\mathtt{divide}</tex>('''int''' a, '''int''' b) delta = 0 '''if''' (a '''mod''' b≠ 0)delta = 1 '''if''' ((a > 0 '''and''' b > 0) '''or''' (a < 0 '''and''' b < 0)) '''return''' [a / b] + delta '''return''' -[|a| / |b|] Такая реализация будет работать за <math>O(n)</math>.
==Динамический convex hull trick==
Заметим, что условия на прямые, что возрастание/убывание <mathtex>k[i]</mathtex> возрастаетна убывание/убывает возрастание и <mathtex>x[i]</mathtex> убывает/возрастает выглядят не достаточно общимиредкими для большинства задач. Как же быть, если Пусть в задаче таких ограничений нет. Иногда можно Первый способ борьбы с этой проблемой - отсортировать прямые входные данные нужным образом, не испортив свойств задачи (пример : задача G отсюда c Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdfСайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>). Но рассмотрим общий случай. Наша задача поменялась следующим образом : поПо-прежнему у нас есть выпуклая оболочкапрямых, имея которую с помощью которой мы за <mathtex>O(logn\log(n))</mathtex> или быстрее можем найти <mathtex>dp[i]</mathtex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить старым описанным ранее способом за <mathtex>O(1)</mathtex> (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4: красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x_1; x_2]</tex>, где <tex>x_1, x_2 \in R</tex> - точки пересечения с некоторыми прямыми, причем <tex>x_2</tex> не обязательно равно <tex>+ \infty</tex>
[[Файл:picture4convexhull.png]]
== Альтернативный подход ==
[[Файл:picture5convexhull.png]]
Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <math>3</math> вектора <math>a, b, c</math>, расположенные как на рис. 5, т.е. точка <math>b</math> не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow [a-b, b-c] < 0 </tex>, то либо <tex>(a, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>, либо <tex>(c, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>.
{{Теорема
|id=th12392.
|statement=Если есть <tex>3</tex> вектора <tex>a, b, c</tex>, таких что <tex>[a-b, b-c] < 0</tex> то либо <math>(a, u) < (b, u)</math>, либо <math>(c, u) < (b, u)</math>, где вектор <math>u = (1; k)</math>.
|proof=По условию теоремы известно, что <tex>[a-b, b-c] < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u) < (a, u) \Leftrightarrow b_{x} + k \cdot b_{y} < c_{x} + k \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) < k \cdot (c_{y} - b_{y})</tex> и при этом <tex>(b, u) < (c, u) \Leftrightarrow b_{x} + k \cdot b_{y} < a_{x} + k \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) > k \cdot (b_{y} - a_{y})</tex>.
Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = k</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.
}}
Из доказанной теоремы и следует корректность алгоритма.
==См. также==
*[[:Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|Выпуклая оболочка]]
*[[:Динамическое_программирование|Динамическое программирование]]
== Примечания ==
<references/>
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Способы оптимизации методов динамического программирования]]