Изменения

Другой способ интерпретировать выражение <tex>dp[i] = \min\limits_{j=0...i-1}(c[j] \cdot a[i] + dp[j])</tex> заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : <tex>dp[j] + a[i] \cdot c[j] = (dp[j], c[j]) \cdot (1, a[i])</tex>, т.е. запишем как скалярное произведение векторов <tex>v[j] = (dp[j], c[j])</tex> и <tex >u[i] = (1, a[i])</tex >. Вектора <tex >v[j] = (dp[j], c[j])</tex> хотелось бы организовать так, чтобы за <tex >O(\log(n))</tex> находить вектор, максимизирующий выражение <tex>v[j] \cdot u[i]</tex>. Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) <tex>j</tex> не может давать более оптимальное значение <tex>v[j] \cdot u[i]</tex> одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов <tex>v[j]</tex>, а ответ на запрос - это поиск <tex>v[j]</tex>, максимизирующего проекцию на <tex>u[i]</tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <tex>(0, 0)</tex> в <tex>(1, a[i])</tex>). Ее можно решить за <tex>O(\log(n))</tex> двумя бинарными или одним тернарным поиском

необходимо показать, что если есть 3 вектора a, b, c, расположенные как на рисунке 5 (т.е. <tex>[a-b, b-c] \leqslant < 0</tex>, где <tex>[u, v]</tex> - модуль векторного произведения векторов <tex>u</tex> и <tex>v</tex>), то либо (a, u[i]) \leqslant < (b, u[i]), либо (c, u[i]) \leqslant < (b, u[i]).

Распишем условие того, что точка b не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex>[a-b, b-c] \leqslant < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) \leqslant < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u[i]) \leqslant < (a, u[i]) \Leftrightarrow b_{x} + a[i] \cdot b_{y} \leqslant < c_{x} + a[i] \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) \leqslant < a[i] \cdot (c_{y} - b_{y})</tex> и <tex>(b, u[i]) \leqslant < (c, u[i]) \Leftrightarrow b_{x} + a[i] \cdot b_{y} \leqslant < a_{x} + a[i] \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) \geqslant > a[i] \cdot (b_{y} - a_{y})</tex>.

Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = a[i]</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex>\leqslant < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> \leqslant < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>\leqslant < a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) \leqslant < a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.