Изменения

== Альтернативный подход ==

Другой способ интерпретировать выражение <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> двумя бинарными или одним тернарным поиском

[[Файл:picture5convexhull.png]]