Изменения

Другой способ интерпретировать выражение <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> хотелось бы организовать так, чтобы за O(logn) находить максимизирующий выражение <math>v[j] * u[i]</math>. Посмотрим на рис. 5. Заметим довольно очевидный факт : красная точка(вектор) j не может давать более оптимальное значение v[j] * u[i] одновременно чем обе синие точки, т.к. v[j] * u[i] - это на самом деле проекция вектора v[j] на u[i]. По этой причине нам достаточно оставить выпуклую оболочку векторов v[j], а ответ на запрос - это поиск v[j], максимизирующего проекцию на u[i]. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из (0, 0) в (1, a[i])). Ее можно решить за O(logn) двумя бинарными или одним тернарным поискомАссимптотика алгоритма по-прежнему составит <math>O(nlognn*log(n))</math>