Изменения

Convex hull переводится с английского как выпуклая оболочка[http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]. Convex hull trick -- один из методов оптимизации динамического программирования[[http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование]], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задачь, решемых методом динамического программирования с <math>O(n^2)</math> до <tex>O(n\cdot\log(n))</tex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO -- национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.

'''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n], '''int''' n) dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex> '''for''' i = 1..n-1 dp[i] = <tex>+\infty</tex> '''for''' j = 0..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]

Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <tex>k[]</tex> и <tex>b[]</tex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<tex>i</tex>-тую) прямую в множество. Пусть сейчас в множестве лежит <tex>sz</tex> прямых (нумерация с 1). Пусть <tex>(xL, yL)</tex> - точка пересечения <tex>sz - 1</tex>-й прямой множества и <tex>sz</tex>-й, а <tex>(xR, yR)</tex> - точка пересечения новой прямой, которую мы хотим добавить в конец множества и <tex>sz</tex>-й. Нас будут интересовать только их <tex>x</tex>-овые координаты <tex>xL</tex> и <tex>xR</tex>, соответственно. Если оказалось, что новая прямая пересекает <tex>sz</tex>-ю прямую выпуклой оболочки позже, чем <tex>sz</tex>-я <tex>sz - 1</tex>-ю, т.е. <tex>(xL >= \geqslant xR)</tex>, то <tex>sz</tex>-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо <tex>xL</tex> не станет меньше <tex>xR.</tex>

Доказательство : Пусть <tex>Y(x) = Kx + B</tex> - уравнение новой прямой, <tex>y[i](x) = K[i]x + B[i]</tex> - уравнения прямых множества. Тогда т.к. <tex>K < K[sz]</tex>, то при <tex>x \in [- \infty; xR] : y[sz](x) <= Y(x)</tex>, а т.к. <tex> K[sz] < K[sz - 1]</tex>, то при <tex>x \in [xL; + \infty] : y[sz - 1](x) >= \geqslant y[sz](x)</tex>. Если <tex>xL < xR</tex>, то при <tex>x \in [xL; xR] : y[sz - 1] >= \geqslant y[sz](x) и Y(x) >= \geqslant y[sz](x)</tex>, т.е. на отрезке <tex>[xL; xR]</tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <tex>xL > xR</tex>, то она ниже всех на отрезке <tex>[xL; xR] = \varnothing </tex>, т.е. её можно удалить из множества

Будем хранить 2 массива : <tex>front[]</tex> - <tex>x</tex>-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при <tex>x</tex> <tex>\in</tex> <tex>[front[i]; front[i + 1])</tex> ) и <tex>st[]</tex> - номера деревьев, соответствующих прямым (т.е. <tex>i</tex>-я прямая множества, где <tex>i</tex> <tex>\in</tex> <tex>[1; sz]</tex> соответствует дереву номер <tex>sz[i]</tex>). Также воспользуемся тем, что <tex>x[i] = a[i]</tex> возрастают (по условию задачи), а значит мы можем искать первое такое <tex>j</tex>, что <tex>x[i] >= \geqslant front[j]</tex> не бинарным поиском, а методом двух указателей за <tex>O(n)</tex> операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые <tex>x[i]</tex>, а значит если <tex>k</tex>-я прямая пересекается с <tex>k+1</tex>-й в точке <tex>z +</tex> <tex>\alpha</tex> (z-целое, <tex>\alpha</tex> <tex>\in</tex> <tex>[0;1)</tex>), то мы будем подставлять в их уравнения <tex>z</tex> или <tex>z + 1</tex>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с <tex>x = z+1</tex>

'''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n], '''int''' n) st[1] = 1 from[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[sz + 1] = x <font color=green>// добавили новую прямую </font > sz = sz + 1

Здесь функция <tex>\mathtt{divide}</tex>(a, b) возвращает нужное(*) округление a / b. Приведем её код :