Изменения

Другой способ интерпретировать выражение <tex>dp[i] = \min_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(logn\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>(1, a[i])</tex>). Ее можно решить за <tex>O(logn\log(n))</tex> двумя бинарными или одним тернарным поискомАсимптотика алгоритма по-прежнему составит <tex>O(nlogn \cdot \log(n))</tex>