动态规划

前面的鸽。

优化类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 模板，虽然它甚至连分块都没卡掉。

\(\color{black}{P2034}\)

首先设计状态，\(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 了。