前面的鸽。
优化类dp
单调队列优化 dp
通常用于解决形如
的 dp 方程优化，计算可以达到 \(\Theta(n).\) 复杂度并不算很高。
以下介绍默认队列中单调不升
先说一下单调队列的思想：
维护一个内容完全满足单调性的队列，其中的元素满足限制（即位置可以保证在 \([i-R,i-L]\)）。
实时更新队列中位置不满足要求的部分，直接弹出即可。
当加入元素时，将队列中大于加入元素的元素全部弹出，因为新加入的元素一定是最新、位置最合适的，可以感性地理解为年纪最小的。
于是把能力比这个元素大的全部弹出，因为这个元素的年纪特性是最合适的，所以在一系列弹出之后一定会加入队列。这个时候这个元素前面的元素一定是比这个元素小的，所以这个队列始终单调。
单调队列通常解决限定长度的最小值，查询全序列所有长度为 \(k\) 的最小值是 \(O(1)\) 的，甚至在线。
属于一种基础的数据结构， \(J\) 组难点。
这个东西可以用各种各样的方式优化 \(dp\) ，总之算是实用的小科技，如果考试的时候想不到 / 打不出来可以用更加暴力的线段树代替，反正只会加一只 \(\log\)。
下面是关键部分代码（单调队列板子）
for(register int i=1;i<=n;++i){
printf("%d\n",a[Q[l]]);
a[i]=re;
while(l<=r&&i-Q[l]>=m) ++l;
while(l<=r&&a[Q[r]]>a[i]) --r;
Q[++r]=i;
}
其中注意单调队列 \(Q\) 中存储的是下标。
例题
介绍一个单调队列优化 dp 模板，虽然它甚至连分块都没卡掉。
首先设计状态，\(dp[i]\) 表示前 \(i\) 个数可以在满足要求的条件下删去数的最小值，转移方程显然是 \(dp[i] = dp[j] + a[i] (j\in\{i-R,i-L\})\)，然后答案就是 \(tot\) 减去 \(\min\{dp[i]\} (i\in\{n-k,n\})\) 其中 \(tot\) 表示所有数的总和。总复杂度 \(O(n)\)\(\color{black}{Link}\)
稍微调试以下边界，然后就可以 AC 了。