Изменения

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