单调性优化 DP

单调队列优化适用于转移窗口连续、且只需窗口最值的 DP，例如 dp[i]=a[i]+max(dp[j])，其中 i-K≤j<i。

单调队列步骤

1. 队首弹出已离开窗口的下标；
2. 用队首对应状态计算 dp[i]；
3. 从队尾弹出不可能优于当前状态的下标；
4. 将 i 入队。

deque<int> q;
for(int i=1;i<=n;i++){
  while(!q.empty() && q.front()<i-K) q.pop_front();
  dp[i]=a[i]+dp[q.front()];
  while(!q.empty() && dp[q.back()]<=dp[i]) q.pop_back();
  q.push_back(i);
}

正确性与复杂度

队列下标递增，dp 值单调递减（求最大值时）；被队尾删去的状态在更晚且更优的状态存在时永远不会成为答案。每个下标最多进出队一次，因此总时间 O(n)、空间 O(K)。

其他单调性

决策点最优位置随状态单调时，可用分治 DP 优化；满足四边形不等式的特定区间 DP 可用 Knuth 优化。它们均须先证明单调决策，不能仅因形式相似而套用。

整理自 XOJ《单调性优化DP》。