Постановка задачи

Пусть $$$w(j, i)$$$ — некоторая функция стоимости, которую мы умеем вычислять за $$$O(1)$$$ и для которой выполняется неравенство четырехугольника:

$$$w(a, c) + w(b, d) \le w(a, d) + w(b, c)$$$, где $$$a \le b \le c \le d$$$.

Наша задача: посчитать динамику вида $$$dp[i] = \min\limits_{0 \le j < i} dp[j] + w(j, i)$$$ (будем считать, что $$$dp[0] = 0$$$) быстрее, чем за $$$O(n^2)$$$, где $$$n$$$ — размер нашей динамики.

Теория

Для начала введем вспомогательную двумерную динамику, которая нам понадобиться только для понимания теории — мы не будем никак её использовать в самом алгоритме.

$$$tmp[i][j] = \min\limits_{0 \le x \le j} dp[x] + w(x, i)$$$; ($$$j < i$$$).

По сути, $$$tmp[i][j]$$$ — это просто промежуточное состояние $$$dp[i]$$$, когда мы его прорелаксировали только через первые $$$(j+1)$$$ индексов. Таким образом, например, $$$tmp[i][i - 1] = dp[i]$$$.

Теперь давайте введем следующую функцию:

$$$k(j, i) = \arg \min\limits_{0 \le x \le j} dp[x] + w(x, i)$$$; ($$$j < i$$$).

Другими словами, $$$k(j, i)$$$ является точкой разреза (точкой оптимума) для $$$tmp[i][j]$$$ — минимальным индексом $$$0 \le x \le j$$$ таким, что $$$tmp[i][j] = dp[x] + w(x, i)$$$.

Заметим, что если мы будет знать значение $$$k(i - 1, i)$$$, то мы сможем за $$$O(1)$$$ посчитать значение $$$dp[i]$$$:

$$$dp[i] = dp[k(i - 1, i)] + w(k(i - 1, i), i)$$$.

Также заметим, что мы можем посчитать значение $$$k(j + 1, i)$$$ через $$$k(j, i)$$$:

То есть чтобы вычислить значение $$$k(j + 1, i)$$$ через $$$k(j, i)$$$, достаточно просто проверить, выполняется ли неравенство $$$dp[j + 1] + w(j + 1, i) < dp[k(j, i)] + w(k(j, i), i)$$$.

Утверждение. Для любого фиксированного $$$j$$$ функция $$$k_j(i) = k(j, i)$$$ является неубывающей для $$$i=(j+1)..n$$$.

Следствие. Если $$$k_{j+1}(i)=j+1$$$, то из-за монотонности $$$k_{j+1}(i+1) \ge j+1 \Rightarrow k_{j+1}(i+1) = j+1$$$. Поскольку $$$k_{j+1}(i)=j+1$$$ или $$$k_{j+1}(i)=k_j(i)$$$, то значения у $$$k_{j+1}$$$ будут такими же, как и у $$$k_j$$$, за исключением некоторого суффикса (возможно, пустого) — значения на нем будут равны $$$(j+1)$$$.

Тогда мы можем легко вычислять все значения $$$k(j, i)$$$. Значения для $$$k(0, i)$$$ мы знаем — они все равны 0. Допустим, что все значения $$$k(x, i)$$$ для $$$x \le j$$$ мы посчитали. Чтобы посчитать значения для $$$k(j + 1, i)$$$, посчитаем значение динамики для $$$dp[j + 1]$$$ (мы можем это сделать за $$$O(1)$$$, так как $$$k(j, j + 1)$$$ уже посчитано), найдем суффикс, на котором все значения будут равны $$$(j+1)$$$ (его можно найти, например, с помощью бинпоиска, проверяя, чему равно значение текущего $$$k(j + 1, mid)$$$), "скопируем" значения $$$k(j, i)$$$ и сделаем присвоение к $$$(j+1)$$$ на суффиксе. О том, как делать это эффективно поговорим в разделе Алгоритм. Заметим, что кроме подсчета $$$k(j, i)$$$ мы также нашли и все значения $$$dp[i]$$$, что от нас и требовалось.

Алгоритм

Будем хранить только для текущего $$$j$$$ значения $$$k(j, i)$$$ в виде дека отрезков равных значений (для каждого отрезка мы будем хранить значения $$$k(j, i)$$$ на нем и его начало). Для того, чтобы посчитать $$$dp[j+1]$$$, мы должны взять просто значение $$$k(j, j + 1)$$$ из дека — оно лежит в самом первом отрезке, так как $$$(j + 1)$$$ — минимальное возможное значение $$$i$$$ для фукнции $$$k_j$$$. Теперь вместо "копирования" мы просто удалим первый элемент из первого отрезка: увеличим значение начала первого отрезка на один. Если отрезок стал пустым, то удалим его. Далее нам нужно найти суффикс, на котором значения функции обновятся. Заметим, что у нас из дека удалится несколько отрезков из конца дека (возможно, все или ни одного). Чтобы проверить, нужно ли удалять последний отрезок из дека, нужно проверить, изменилось ли значение фукнции на $$$(j + 1)$$$ в начале отрезка. Будем удалять отрезок из конца дека, пока дек не пустой и утверждение верно. Далее с помощью бинпоиска находим начало нового отрезка и добавляем его в дек (крайними случаями будут, если дек пустой или длина нового отрезка равна 0). Для некоторых задач мы можем без бинпоиска найти начало отрезка — это улучшит асимптотику. Для этого нам нужно уметь считать функцию $$$D(j, i)$$$ — минимальное значение $$$x$$$ такое, что $$$dp[j] + w(j, x) \ge dp[i] + w(i, x)$$$.

Пример реализации можно найти ниже или здесь (но там рассматривается немного другая реализация).

Пример

Рассмотрим задачу 319C - Калила и Димна на лесозаготовках.

Эту задачу можно свести к следующему подсчету динамики:

$$$dp[i]=\min\limits_{j<i} dp[j] + b[j] \cdot a[i]$$$,

Причем для каждого $$$i < j$$$ верно, что $$$a[i] < a[j]$$$ и $$$b[i] > b[j]$$$.

Введем тогда следующую функцию стоимости:

$$$w(j, i) = b[j] \cdot a[i]$$$.

Заметим, что для нее выполняется неравенство четырехугольника по транснеравентсву, поэтому мы можем применить 1D1D-оптимизацию.

Пример возможной реализции за $$$O(n\log{n})$$$: 125522308.

Чтобы написать решение за линию, можно искать для функции $$$D(j, i)$$$ не минимальное значение индекса, а минимальное число $$$x$$$ такое, что $$$dp[j] + b[j] \cdot x > dp[i] + b[i] \cdot x$$$. Тогда для дека мы также будем хранить тогда не начало-индекс, а начало-число. Заметим, что работа именно с $$$a[i]$$$ нам нужна только для подсчета значений динамики $$$dp[i]$$$, поэтому мы можем немного изменить наш алгоритм, сказав, что мы не будем уменьшать никакие длины отрезков из начала, а будем удалять отрезки из начала, пока они левее на числовой прямой, чем текущее $$$a[j]$$$. Значение $$$D(j, i)$$$ легко посчитать — оно равно $$$\frac{dp[i] - dp[j]}{b[j] - b[i]}$$$.

Пример возможной реализации за $$$O(n)$$$: 125523046.

Источники: 1 2.