Монотонная очередь в ДП: как сделать sliding window minimum для перехода?
ДП вида dp[i] = min_{i-k <= j < i} (dp[j]) + c[i] — минимум по окну фиксированной ширины k. Наивно O(n·k) → TLE. Как ускорить до O(n) монотонной очередью?
2 ответа
Это классический sliding window minimum. Держим deque индексов, в котором значения dp[idx] монотонно возрастают (минимум всегда спереди). Перед использованием выкидываем спереди индексы, вышедшие из окна [i-k, i-1]. При добавлении нового dp[j] выкидываем сзади все, что больше или равно ему — они уже никогда не станут минимумом, пока жив новый меньший.
deque<int> dq; // индексы j, dp[j] возрастает
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int j = i - 1; // только что готовый кандидат
while (!dq.empty() && dp[dq.back()] >= dp[j]) dq.pop_back();
dq.push_back(j);
while (dq.front() < i - k) dq.pop_front(); // выкидываем устаревшие
dp[i] = dp[dq.front()] + c[i];
}
Сложность O(n) время (каждый индекс входит и выходит из deque по разу), O(k) память. Грабли: порядок «сначала добавить нового кандидата i-1, потом подрезать спереди по границе окна» важен; и граница окна < i - k vs <= i - k зависит от того, включается ли dp[i-k] — частая причина off-by-one и WA.
Когда применять именно очередь, а не дерево отрезков: монотонная очередь работает только если окно сдвигается монотонно (его левая и правая границы только растут). Если запросы минимума по произвольным окнам — нужно RMQ (sparse table за O(1) на запрос после O(n log n) препроцессинга) или дерево отрезков. Для «скользящего» перехода в ДП очередь оптимальна: O(n) и маленькая константа. Если минимум — по окну, чья ширина зависит от значения (например dp[j]+w[j] >= i), очередь тоже годится, но границу выкидывания считай по этому условию, а не по фиксированному k.