Изменения

Другой способ интерпретировать выражение <math>dp[i] = max(dp[j] + a[i] * c[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) двумя бинарными или одним тернарным поиском