Изменения
→Альтернативный подход
== Альтернативный подход ==
Другой способ интерпретировать выражение <tex>dp[i] = \min_{j=0...i-1}(c[j]*a[i] + dp[j])</tex> заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : <tex>dp[j] + a[i] * c[j] = (dp[j], c[j]) * (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(logn)</tex> находить вектор, максимизирующий выражение <tex>v[j] * u[i]</tex>. Посмотрим на рис. 5. Заметим довольно интуитивно очевидный факт : красная точка(вектор) <tex>j</tex> не может давать более оптимальное значение <tex>v[j] * u[i]</tex> одновременно чем обе синие точки, т.к. <tex>v[j] * u[i]</tex> - это на самом деле проекция вектора <tex>v[j]</tex> на <tex>u[i]</tex>. По этой причине нам достаточно оставить выпуклую оболочку векторов <tex>v[j]</tex>, а ответ на запрос - это поиск <tex>v[j]</tex>, максимизирующего проекцию на <tex>u[i]</tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <tex>(0, 0)</mathtex в <tex>(1, a[i])</tex>). Ее можно решить за <tex>O(logn)</tex> двумя бинарными или одним тернарным поиском
Асимптотика алгоритма по-прежнему составит <tex>O(nlog(n))</tex>
[[Файл:picture5convexhull.png]]
Доказательство :
необходимо показать, что если есть 3 вектора a, b, c, расположенные как на рисунке 5 (т.е. <tex>[a-b, b-c] < 0</tex>, где <tex>[u, v]</tex> - модуль векторного произведения векторов <tex>u</tex> и <tex>v</tex>), то либо (a, u[i]) < (b, u[i]), либо (c, u[i]) < (b, u[i]).
Распишем условие того, что точка b не лежит на выпуклой оболочке векторов<tex> 0, a, b, c </tex> : <tex>[a-b, b-c] < 0 <=> (a_{x} - b_{x})*(b_{y} - c_{y}) < (a_{y} - b_{y}) * (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u[i]) < (a, u[i]) <=> b_{x} + a[i]*b_{y} < c_{x} + a[i] * c_{y} <=> (b_{x} - c_{x}) < a[i] * (c_{y} - b_{y})</tex> и <tex>(b, u[i]) < (c, u[i]) <=> b_{x} + a[i] * b_{y} < a_{x} + a[i] * a_{y} <=> (a_{x} - b_{x}) > a[i] * (b_{y} - a_{y})</tex>. Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] * (a_{y} - b_{y}) * (c_{y} - b_{y}) = a[i] * (b_{y} - a_{y}) * (b_{y} - c_{y}) < (a_{x} - b_{x}) * (b_{y} - c_{y}) < (a_{y} - b_{y}) * (b_{x} - c_{x}) < a[i] * (a_{y} - b_{y}) * (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] * (a_{y} - b_{y}) * (c_{y} - b_{y}) < a[i] * (a_{y} - b_{y}) * (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.
