Изменения

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