单调队列优化DP

参考《算法竞赛进阶指南》、AcWing题库

“单调栈” 和 “单调队列” 这两种思想的本质都是借助单调性, 及时排除不可能的决策, 保持候选集合的高度有效性和秩序性。仔细回顾 “最大子序和” 这道例题, 该问题的答案可以形式化表述为:

$a n s=\max _{1 \leq i \leq N}\left\{S[i]-\min _{i-M \leq j \leq i-1}\{S[j]\}\right\}$

此处的 $i$ 非常类似于动态规划的 “状态”, $j$ 则类似于动态规划的 “决策”。我们从小到大枚举每个 $i \in[1, N]$ , 当 $i$ 增大 1 时, $j$ 的取值范围 $[i-M, i-1]$ 的上、下界同时增大 1 , 变为 $[i-M+1, i]$ 。这意味着不仅有一个新的决策 $j=i$ 进入了候选集合, 也应该把过时的决策 $j=i-M$ 从候选集合中排除。单调队列非常适合优化这种决策取值范围的上、下界均单调变化, 每个决策在候选集合中插入或删除至多一次的问题。

类比 “最大子序和”一题的思想, 尝试解答下面几道例题。

298. 围栏

题目描述

有 $N$ 块木板从左到右排成一行，有 $M$ 个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。

第 $i$ 个木匠要么不粉刷，要么粉刷包含木板 $S_i$ 的，长度不超过 $L_i$ 的连续的一段木板，每粉刷一块可以得到 $P_i$ 的报酬。

不同工匠的 $S_i$ 不同。

请问如何安排能使工匠们获得的总报酬最多。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

接下来 $M$ 行，每行包含三个整数 $L_i,P_i,S_i$ 。

输出格式

输出一个整数，表示结果。

数据范围

$1 \le N \le 16000$ ,
$1 \le M \le 100$ ,
$1 \le P_i \le 10000$

输入样例：

输出样例：

算法分析

先把所有工匠按照 $S_{i}$ 排序, 这样一来, 每个工匠粉刷的木板一定在上一个工匠粉刷的木板之后，使我们能够按顺序进行线性 DP。

设 $F[i, j]$ 表示安排前 $i$ 个工匠粉刷前 $j$ 块木板 (可以有空着不刷的木板), 工匠们能获得的最多报酬。

第 $i$ 个工匠可以什么也不刷, 此时 $F[i, j]=F[i-1, j]$ 。
第 $j$ 块木板可以空着不刷, 此时 $F[i, j]=F[i, j-1]$ 。
第 $i$ 个工匠粉刷第 $k+1$ 块到第 $j$ 块木板。根据题意, 该工匠粉刷总数不能超过 $L_{i}$ , 且必须粉刷 $S_{i}$ , 所以需要满足: $k+1 \leq S_{i} \leq j$ 并且 $j-k \leq L_{i}$ 。于是, 有状态转移方程:

$F[i, j]=\max _{j-L_{i} \leq k \leq S_{i}-1}\left\{F[i-1, k]+P_{i} *(j-k)\right\} \text {, 其中 } j \geq S_{i}$

我们重点来看这个方程如何优化。首先, 我们多次提到, 在考虑内层循环 $j$ 以及决策 $k$ 时, 可把外层循环变量 $i$ 看作定值。这样一来, 状态转移方程中的各项可分为两部分：

$P_{i} * j$ , 除定值 $i$ 外, 只有状态变量 $j$ 。
$F[i-1, k]-P_{i} * k$ , 除定值 $i$ 外, 只有决策变量 $k$ 。

状态转移方程可改写为:

$F[i, j]=P_{i} * j+\max _{j-L_{i} \leq k<S_{i}-1}\left\{F[i-1, k]-P_{i} * k\right\} \text {, 其中 } j \geq S_{i}$

当 $j$ 增大时, $k$ 的取值范围上界 $S_{i}-1$ 不变, 下界 $j-L_{i}$ 变大。按与 “最大子序和" 一题类似的想法, 我们比较一下任意两个决策 $k_{1}$ 和 $k_{2}$ 。不妨设 $k_{1}<k_{2} \leq$ $s_{i}-1$ 。

因为 $k_{2}$ 比 $k_{1}$ 更靠后, 所以随着 $j$ 的增加, $k_{1}$ 会比 $k_{2}$ 更早从范围 $\left[j-L_{i}, S_{i}-1]\right.$ 中被排除。如果还满足 $F\left[i-1, k_{1}\right]-P_{i} * k_{1} \leq F\left[i-1, k_{2}\right]-P_{i} * k_{2}$ , 那么就意味着 $k_{2}$ 不但比 $k_{1}$ 更优, 还比 $k_{1}$ 的存活时问更长。在这种情况下, $k_{1}$ 就是一个无用的决策, 应该被直接排除出候选集合。

综上所述, 我们可以维护一个决策点 $k$ 单调递增, 数值 $F[i-1, k]-P_{i} * k$ 单调递减的队列。只有这个队列中的决策才有可能在某一时刻成为最优决策。这个单调队列支持如下几种操作:

当 $j$ 变大时, 检查队头元素, 把小于 $j-L_{i}$ 的决策出队。
需要查询最优决策时, 队头即为所求。
有一个新的决策要加入候选集合时, 在队尾检查 $F[i-1, k]-P_{i} * k$ 的单调性, 把无用决策从队尾直接出队, 最后把新决策加入队列。

在本题中具体来说, 当内层循环开始时 $\left(j=S_{i}\right)$ , 建立一个空的单调队列, 把 $\left[\max \left(S_{i}-L_{i}, 0\right), S_{i}-1\right]$ 中的决策依次加入候选集合(执行操作 3 $)$ 。对于每个 $j=S_{i} \sim N$ , 先在队头检查决策合法性 (操作 1), 然后取队头为最优决策 (操作 2 ) 进行状态转移。

因为每个决策至多入队、出队一次, 故转移的时间复杂度均推 $O(1)$ 。整个算法的时间复杂度为 $O(N M)$ 。

struct rec{ int L, P, S; } a[110];
int n, m;
int f[110][16010], q[16010];

bool operator <(rec a, rec b) {
	return a.S < b.S;
}

int calc(int i, int k) {
	return f[i - 1][k] - a[i].P * k;
}

int main()  {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &a[i].L, &a[i].P, &a[i].S);
	sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; i++) {
		// 初始化单调队列
		int l = 1, r = 0;
		// 把最初的候选集合插入队列
		for (int k = max(0, a[i].S - a[i].L); k <= a[i].S - 1; k++) {
			// 插入新决策，维护队尾单调性
			while (l <= r && calc(i, q[r]) <= calc(i, k)) r--;
			q[++r] = k;
		}
		for (int j = 1; j <= n; j++) {
			// 不粉刷时的转移
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			// 粉刷第k+1~j块木板时的转移
			if (j >= a[i].S) {
				// 排除队头不合法决策
				while (l <= r && q[l] < j - a[i].L) l++;
				// 队列非空时，取队头进行状态转移
				if (l <= r) f[i][j] = max(f[i][j], calc(i, q[l]) + a[i].P * j);
			}
		}
	}
	cout << f[m][n] << endl;
}

Solution

299. 裁剪序列

题目描述

给定一个长度为 $N$ 的序列 $A$ ，要求把该序列分成若干段，在满足“每段中所有数的和”不超过 $M$ 的前提下，让“每段中所有数的最大值”之和最小。

试计算这个最小值。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

第二行包含 $N$ 个整数，表示完整的序列 $A$ 。

输出格式

输出一个整数，表示结果。

如果结果不存在，则输出 $-1$ 。

数据范围

$0 \le N \le 10^5$ ,
$0 \le M \le 10^{11}$ ,
序列A中的数非负，且不超过 $10^6$

输入样例：

1 2	8 17 2 2 2 8 1 8 2 1

输出样例：

算法分析

设 $F[i]$ 表示把前 $i$ 个数分成若干段, 在满足每段中所有数的和不超过 $M$ 的前提下, 各段的最大值之和最小是多少。容易写出状态转移方程:

$F[i]=\min _{0 \leq j<i \text { 并且 } \sum_{k=j+1}^{i} A_{k} \leq M}\left\{F[j]+\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}\right\}$

若采用枚举决策 $j$ 的方法, 时间复杂度为 $\mathrm{O}\left(\dot{N}^{2}\right)$ 。然而, 该方程似乎很难进行优化, 因为 $\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}$ 不容易用一个简单的多项式来表示, 不容易找到单调性。我们曾多次强调, DP 转移优化的指导思想就是及时排除不可能的决策, 保持候选集合的高度有效性和秩序性。本着这个原则, 我们考虑一个决策 $j$ 何时是必要的。

引理:

在上述方程中, 若 $j(0 \leq j<i)$ 可能成为最优决策, 则除了 $\sum_{k=j+1}^{i} A_{k} \leq M$ 外, 必然还满足以下两个条件之一:

$A_{j}=\max _{j \leq k \leq i}\left\{A_{k}\right\}$

$\sum_{k=j}^{i} A_{k}>M$ (即 $j$ 是满足 $\sum_{k=j+1}^{i} A_{k} \leq M$ 的最小的 $j$ )

证明:

反证法。假设两个条件都不满足, 即 $A_{j}<\max _{j \leq k \leq i}\left\{A_{k}\right\}$ 并且 $\sum_{k=j}^{i} A_{k} \leq M$ 。由此可知 $\max _{j \leq k \leq i}\left\{A_{k}\right\}=\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}$ 。另外, $F$ 数组显然具有单调性, 即 $F[j-1] \leq$ $F[j]$ (多一个数, 答案肯定更大)。于是:

$F[j-1]+\max _{j \leq k \leq i}\left\{A_{k}\right\} \leq F[j]+\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}$

上式的含义就是决策 $j-1$ 比 $j$ 更优。而决策的取值范围是 $0 \leq j<i, j-1$ 比 $j$ 更容易满足这个条件。所以, 上式与 $j$ 可能成为最优决策矛盾, 故假设不成立。证毕。

引理中的第 2 个条件比较简单, 只需预处理出对于每个 $i$ , 满足 $\sum_{k=j+1}^{i} A_{k} \leq M$ 的最小的 $j$ , 记为 $C[i]$ 。在计算 $F[i]$ 时, 从 $C[i]$ 进行一次转移即可。下面我们单独讨论满足引理中第 1 个条件的决策 $j$ 的维护方法。

根据引理, 当一个新的决策 $j_{2}$ 插入候选集合时, 若候选集合中已有的决策 $j_{1}$ 满足条件 $j_{1}<j_{2}$ 并且 $A_{j_{1}} \leq A_{j_{2}}$ , 则 $j_{1}$ 就是无用决策, 可被排除。

综上所述, 我们可以维护一个决策点 $j$ 单调递增、数值 $A_{j}$ 单调递减的队列, 只有该队列中的元素才可能成为最优决策。

与上一道题目不同的是, 该队列只是一个 $A_{j}$ 单调递减的队列, 关于转移方程等式右边的 $F[j]+\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}$ 并没有单调性。所以我们不能简单地取队头为最优决策, 而是要再加一个额外的数据结构 (例如二叉堆)。二叉堆与单调队列保存相同的候选集合, 该插入时一起插入, 该删除时一起删除 (或用 “懒惰删除法”, 参见 $0 \times 71$ 节), 只不过单调队列以 $A_{j}$ 递减作为比较大小的依据, 二叉堆以 $F[j]+\max _{j+1 \leq k s i}\left\{A_{k}\right\}$ 作为比较大小的依据, 保证能快速在候选集合中查询最值。事实上, 我们一般称这种做法为 “二叉堆与单调队列建立了映射关系”。

最后, 关于 $\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}$ 的计算有两种方法: 第一种是按照区间最值问题, 直接用 $\mathrm{ST}$ 算法预处理, 支持 $O(1)$ 查询; 第二种是仔细发掘本题中单调队列的性质, 我们可以发现, 队列中某一项的 $\max _{j+1 s k s i}\left\{A_{k}\right\}$ 的结果其实就是队列中下一个元素的 $A$ 值。

在整个算法中, 每个 $j$ 至多在单调队列和二叉堆中插入和删除一次, 故时间复杂度为 $O(N \log N)$ 。

Solution

6. 单调队列优化多重背包

题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数， $N，V$ $(0 \lt N \le 1000$ , $0 \lt V \le 20000)$ ，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$ ，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N \le 1000$
$0 \lt V \le 20000$
$0 \lt v_i, w_i, s_i \le 20000$

提示

本题考查多重背包的单调队列优化方法。

输入样例

输出样例：

算法分析

我们已经介绍了多重背包问题的朴素解法和二进制拆分解法。若使用单调队列, 可以把求解多重背包问题的复杂度进一步优化到 $O(N M)$ 。

在背包的朴素解法中, DP 数组省略了 “阶段” 这一维。当外层循环进行到 $i$ 时, $F[j]$ 表示从前 $i$ 种物品中选出若干个放入背包, 体积之和为 $j$ 时, 价值之和最大是多少。倒序循环 $j$ , 在状态转移时, 考虑选取第 $i$ 个物品的个数 $c n t$ :

$F[j]=\max _{1 \leq c n t \leq c_{l}}\left\{F\left[j-c n t * V_{i}\right]+c n t * W_{i}\right\}$

画出能够转移到状态 $j$ 的决策候选集合 $\left\{j-c n t * V_{i} \mid 1 \leq c n t \leq C_{i}\right\}$ :

当循环变量 $j$ 减小 $1$ 时:

可以发现, 相邻两个状态 $j$ 和 $j-1$ 对应的决策候选集合没有重叠, 很难快速地从 $j-1$ 对应的集合得到 $j$ 对应的集合。

但是, 我们试着考虑一下状态 $j$ 和 $j-V_{i}$ :

这两者对应的决策候选集合之间的关系, 与我们前面讲解的单调队列题目非常相似, 只有一个新决策加入候选集合、一个已有决策被排除。所以，我们应该把状态 $j$ 按照除以 $V_{i}$ 的余数分组, 对每一组分别进行计算, 不同组之间的状态在阶段 $i$ 不会互相转移:

余数为 $0 \longmapsto 0, V_{i}, 2 V_{i}, \cdots$
余数为 $1 \longmapsto1 ,1+V_{i}, 1+2 V_{i}, \cdots$
$\cdots$
余数为 $V_{i} - 1 \longmapsto \left(V_{i}-1\right),\left(V_{i}-1\right)+V_{i},\left(V_{i}-1\right)+2 V_{i}, \cdots$

把 “倒序循环 $j$ ” 的过程, 改为对每个余数 $u \in\left[0, V_{i}-1\right]$ , 倒序循环 $p=\lfloor(M-$ $\left.u) / V_{i}\right\rfloor \sim 0$ , 对应的状态就是 $j=u+p * V_{i}$ 。第 $i$ 种物品只有 $C_{i}$ 个, 故能转移到 $j=$ $u+p * V_{i}$ 的决策候选集合就是 $\left\{u+k * V_{i} \mid p-C_{i} \leq k \leq p-1\right\}$ 。写出新的状态转移方程 :

$F\left[u+p * V_{i}\right]=\max _{p-C_{i} \leq k \leq p-1}\left\{F\left[u+k * V_{i}\right]+(p-k) * W_{i}\right\}$

$k$ 的取值范围：因为省略了 “状态” 维度，所以我们可以在上一阶段 $f$ 数组的基础上更新取大值，这样就不必考虑 “不选第 $i$ 个物品", 即 $k=p$ 的情况。

与本节的 “ Fence"一题类似, 把外层循环 $i$ 和 $u$ 看作定值, 当内层循环变量 $p$ 减小 1 时，决策 $k$ 的取值范围 $\left[p-C_{i}, p-1\right]$ 的上、下界均单调减小。状态转移方程等号右侧的式子仍然分为两部分, 仅包含变量 $p$ 的 $p * W_{i}$ 和仅包含变量 $k$ 的 $F\left[u+k * V_{i}\right]-k * W_{i}$ 。综上所述, 我们可以建立一个决策点 $k$ 单调递减、数值 $F[u+ \left.k * V_{i}\right]-k * W_{i}$ 单调递减的队列, 用于维护候选集合。对于每个 $p$ , 执行单调队列的三个惯例操作:

检查队头合法性, 把大于 $p-1$ 的决策点出队。
取队头为最优决策, 更新 $F\left[u+p * V_{i}\right]$ 。
把新决策 $k=p-C_{i}-1$ 插入队尾, 入队前检查队尾单调性, 排除无用决策。

整个算法的时间复杂度为 $\mathrm{O}(N M)$ 。

int calc(int i, int u, int k) {
	return f[u + k*V[i]] - k*W[i];
}

int main() {
	cin >> n >> m;
	memset(f, 0xcf, sizeof(f)); // -INF
	f[0] = 0;
	// 物品种类
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &V[i], &W[i], &C[i]);
		// 除以V[i]的余数
		for (int u = 0; u < V[i]; u++) {
			// 建立单调队列
			int l = 1, r = 0;
			// 把最初的候选集合插入队列
			int maxp = (m - u) / V[i];
			for (int k = maxp - 1; k >= max(maxp - C[i], 0); k--) {
				while (l <= r && calc(i, u, q[r]) <= calc(i, u, k)) r--;
				q[++r] = k;
			}
			// 倒序循环每个状态
			for (int p = maxp; p >= 0; p--) {
				// 排除过时决策
				while (l <= r && q[l] > p - 1) l++;
				// 取队头进行状态转移
				if (l <= r)
					f[u + p*V[i]] = max(f[u + p*V[i]], calc(i, u, q[l]) + p*W[i]);
				// 插入新决策，同时维护队尾单调性
				if (p - C[i] - 1 >= 0) {
					while (l <= r && calc(i, u, q[r]) <= calc(i, u, p - C[i] - 1)) r--;
					q[++r] = p - C[i] - 1;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) ans = max(ans, f[i]);
	cout << ans << endl;
}

单调队列优化 DP 模型总结

最后, 我们对单调队列优化 DP 的模型进行总结。我们重新写出上面三道例题的状态转移方程:

题目	状态转移方程	定值（外层循环）	状态变量（内层循环）	决策变量
最大子序列和	$a n s=\max _{1 \leq i \leq N}\left\{S[i]-\min _{i-M \leq j \leq i-1}\{S[j]\}\right\}$		$i$	$j$
围栏	$F[i, j]=\max _{j-L_{i} \leq k \leq S_{i}-1}\left\{F[i-1, k]+P_{i} *(j-k)\right\} \text {, 其中 } j \geq S_{i}$	$i$	$j$	$k$
裁剪序列	$F[i]=\min _{0 \leq j<i \text { 并且 } \sum_{k=j+1}^{i} A_{k} \leq M}\left\{F[j]+\max _{j+1 \leq k \leq i}\left\{A_{k}\right\}\right\}$		$i$	$j$
多重背包	$F\left[u+p * V_{i}\right]=\max _{p-C_{i} \leq k \leq p-1}\left\{F\left[u+k * V_{i}\right]+(p-k) * W_{i}\right\}$	$i,u$	$p$	$k$

只关注 “状态变量” “决策变量” 及其所在的维度, 这些状态转移方程都可以大致归为如下形式 (除第三个方程稍有不同):

$F[i]=\min _{L(i) \leq j \leq R(i)}\{F[j]+\operatorname{val}(i, j)\}$

上式所代表的问题覆盖范围广泛, 是 DP 中一类非常基本、非常重要的模型。这种模型也被称为 1D/1D 的动态规划。它是一个最优化问题, $L(i)$ 和 $R(i)$ 是关于变量 $i$ 的一次函数, 限制了决策 $j$ 的取值范围, 并保证其上下界变化具有单调性。 $val (i, j)$ 是一个关于变量 $i$ 和 $j$ 的多项式函数, 通常是决定我们采用何种优化策略的关键之处。

回想前面三道例题的解法, 我们都把 $v a l(i, j)$ 分成了两部分, 第一部分仅与 $i$ 有关, 第二部分仅与 $j$ 有关。对于每个 $i$ , 无论采取哪个 $j$ 作为最优决策, 第一部分的值都是相等的, 可以在选出最优决策更新 $F[i]$ 时再进行计算、累加。而当 $i$ 发生变化时, 第二部分的值不会发生变化, 从而保证原来较优的决策, 在 $i$ 改变后仍然较优, 不会产生乱序的现象。于是, 我们就可以在队列中维护第二部分的单调性, 及时排除不可能的决策, 让 DP 算法得以高效进行。所以, 在上述模型中, 多项式 $val (i, j)$ 的每一项仅与 $i$ 和 $j$ 中的一个有关, 是使用单调队列进行优化的基本条件。

135. 最大子序和

题目描述

输入一个长度为 $n$ 的整数序列，从中找出一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 $1$ 。

输入格式

第一行输入两个整数 $n,m$ 。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1 \le n,m \le 300000$

输入样例：

1 2	6 4 1 -3 5 1 -2 3

输出样例：

算法分析

计算 “区间和” 的问题, 一般转化为 “两个前缀和相减” 的形式进行求解。我们先求出 $S[i]$ 表示序列里前 $i$ 项的和, 则连续子序列 $[L, R]$ 中数的和就等于 $S[R]-$ $S[L-1]$ 。那么原问题可以转化为: 找出两个位置 $x, y$ , 使 $S[y]-S[x]$ 最大并且 $y- x \leq M$ 。

首先我们枚举右端点 $i$ , 当 $i$ 固定时, 问题就变为: 找到一个左端点 $j$ , 其中 $j \in[i-m, i-1]$ 并且 $S[j]$ 最小。

不妨比较一下任意两个位置 $j$ 和 $k$ , 如果 $k<j<i$ 并且 $S[k] \geq S[j]$ , 那么对于所有大于等于 $i$ 的右端点, $k$ 永远不会成为最优选择。这是因为不但 $S[k]$ 不小于 $S[j]$ , 而且 $j$ 离 $i$ 更近, 长度更不容易超过 $M$ , 即 $j$ 的生存能力比 $k$ 更强。所以当 $j$ 出现后, $k$ 就完全是一个无用的位置。

以上比较告诉我们, 可能成为最优选择的策略集合一定是一个 “下标位置递增、对应的前缀和 $S$ 的值也递增” 的序列。我们可以用一个队列保存这个序列。随着右端点变从前向后扫描, 我们对每个 $i$ 执行以下三个步骤:

判断队头决策与 $i$ 的距离是否超出 $M$ 的范围, 若超出则出队。
此时队头就是右端点为 $i$ 时, 左端点 $j$ 的最优选择。
不断删除队尾决策, 直到队尾对应的 $S$ 值小于, $S[i]$ 。然后把 $i$ 作为一个新的决策入队。

int l = 1, r = 1;
q[1] = 0; // save choice j=0
for(int i = 1; i <= n; i++) {
	while (l <= r && q[l] < i - m) l++;
	ans = max(ans, sum[i] - sum[q[l]]);
	while (l <= r && sum[q[r]] >= sum[i]) r--;
	q[++r] = i;
}

这就是著名的单调队列算法, 因为每个元素至多入队一次、出队一次, 所以整个算法的时间复杂度为 $O(N)$ 。它的思想也是在决策集合 (队列) 中及时排除一定不是最优解的选择。单调队列是优化动态规划的一个重要手段。

Solution

#include <iostream>
using namespace std;

const int N = 300010, INF = 0x3f3f3f3f;

int n, m;
int s[N], q[N], hh = 0, tt = -1;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    s[i] += s[i - 1];
  }
  
  int maxv = -INF;
  q[++tt] = 0;
  for (int i = 1; i <= n; ++i) {
    if (hh <= tt && q[hh] < i - m) ++hh;
    maxv = max(maxv, s[i] - s[q[hh]]);
    while (hh <= tt && s[i] <= s[q[tt]]) --tt;
    q[++tt] = i;
  }
  
  cout << maxv;
}

1087. 修剪草坪

题目描述

在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。

现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。

然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。

FJ 有 $N$ 只排成一排的奶牛，编号为 $1$ 到 $N$ 。

每只奶牛的效率是不同的，奶牛 $i$ 的效率为 $E_i$ 。

编号相邻的奶牛们很熟悉，如果 FJ 安排超过 $K$ 只编号连续的奶牛，那么这些奶牛就会罢工去开派对。

因此，现在 FJ 需要你的帮助，找到最合理的安排方案并计算 FJ 可以得到的最大效率。

注意，方案需满足不能包含超过 $K$ 只编号连续的奶牛。

输入格式

第一行：空格隔开的两个整数 $N$ 和 $K$ ；

第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $E_i$ 。

输出格式

共一行，包含一个数值，表示 FJ 可以得到的最大的效率值。

数据范围

$1 \le N \le 10^5$ ,
$0 \le E_i \le 10^9$

输入样例：

输出样例：

样例解释

FJ 有 5 只奶牛，效率分别为 1、2、3、4、5。

FJ 希望选取的奶牛效率总和最大，但是他不能选取超过 2 只连续的奶牛。

因此可以选择第三只以外的其他奶牛，总的效率为 1 + 2 + 4 + 5 = 12。

算法分析

这里提供一个转化的思路，题目要求最多连续选k个使效率最大
可以转化为每k + 1个里必须不选 1 个，使不选的总效率最小，最后用总效率减去不选的效率即可

f[i] 表示不选第 i 个的最小不选效率，从前k + 1个里转移即可，可以参考烽火传递这道题

Solution

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n, k;
long long f[N], w[N];
int q[N], hh = 0, tt = -1;

int main() {
  cin >> n >> k;
  long long sum = 0; // 全选的效率
  for (int i = 1; i <= n; ++i) cin >> w[i], sum += w[i];
  
  q[++tt] = 0;
  for (int i = 1; i <= n; ++i) {
    if (hh <= tt && q[hh] < i - k - 1) ++hh;
    f[i] = f[q[hh]] + w[i];
    while (hh <= tt && f[q[tt]] >= f[i]) --tt;
    q[++tt] = i;
  }
  
  long long minv = 9e18;
  for (int i = n - k; i <= n; ++i) minv = min(minv, f[i]);
  
  cout << sum - minv;
}

1088. 旅行问题

题目描述

John 打算驾驶一辆汽车周游一个环形公路。

公路上总共有 $n$ 个车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。

John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。

在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

输入格式

第一行是一个整数 $n$ ，表示环形公路上的车站数；

接下来 $n$ 行，每行两个整数 $p_i,d_i$ ，分别表示表示第 $i$ 号车站的存油量和第 $i$ 号车站到 顺时针方向 下一站的距离。

输出格式

输出共 $n$ 行，如果从第 $i$ 号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第 $i$ 行输出 TAK，否则输出 NIE。

数据范围

$3 \le n \le 10^6$ ,
$0 \le p_i \le 2 \times 10^9$ ,
$0 \le d_i \le 2 \times 10^9$

输入样例：

输出样例：

TAK
NIE
TAK
NIE
TAK

算法分析

顺时针

每个点i表示从i点加oil[i]的油再耗dist[i]的油所剩的油量,即oil[i] - dist[i]

1、计算出油量的前缀和
2、从某个点i出发，顺时针走一圈，在过程中油量始终 >= 0，等价于在[i,i + n - 1]中，对任意的j,i <= j <= i + n - 1，均有s[j] - s[i - 1] >= 0，即i固定，找s[j]的最小值，即从[i,i + n - 1]中找到滑动窗口的最小值
3、由于2操作，需要对i进行反向遍历，即从n * 2遍历到1，又由于i <= j <= i + n - 1，遍历到i时需要用到i位置的值，因此找[i,i + n - 1]区间最小值时需要在while后面的语句找

逆时针

每个点i表示从i点加oil[i]的油再耗dist[i - 1]的油所剩的油量,即oil[i] - dist[i - 1]，其中1号点浩的是dist[n]的油，因此需要初始化dist[0] = dist[n]

1、计算出油量的后缀和
2、从某个点i出发，逆时针走一圈，在过程中油量始终 >= 0，等价于在[i - n + 1,i]中，对任意的j,i - n + 1 <= j <= i，均有s[j] - s[i + 1] >= 0，即i固定，找s[j]的最小值，即从[i - n + 1,i]中找到滑动窗口的最小值
3、由于2操作，需要对i进行正向遍历，即从1遍历到n * 2，又由于i - n + 1 <= j <= i，遍历到i时需要用到i位置的值，因此找[i - n + 1,i]区间最小值时需要在while后面的语句找

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;

int n;
int p[N], d[N];
long long s[N];
int q[N], hh = 0, tt = -1;
bool ans[N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i] >> d[i];
    s[i] = s[i + n] = p[i] - d[i];
  }
  for (int i = 1; i <= 2 * n; ++i) s[i] += s[i - 1];
  
  for (int i = 2 * n; i; --i) {
    if (hh <= tt && q[hh] >= i + n) ++hh;
    while (hh <= tt && s[q[tt]] >= s[i]) --tt;
    q[++tt] = i;
    if (i <= n && s[q[hh]] - s[i - 1] >= 0) ans[i] = true;
  }
  
  
  d[0] = d[n];
  for (int i = 1; i <= n; ++i) s[i] = s[i + n] = p[i] - d[i - 1];
  for (int i = 2 * n; i; --i) s[i] += s[i + 1];
  
  hh = 0, tt = -1;
  for (int i = 1; i <= 2 * n; ++i) {
    if (hh <= tt && q[hh] <= i - n) ++hh;
    while (hh <= tt && s[q[tt]] >= s[i]) --tt;
    q[++tt] = i;
    if (i > n && s[q[hh]] - s[i + 1] >= 0) ans[i - n] = true; 
  }
  
  for (int i = 1; i <= n; ++i) {
    if (ans[i]) cout << "TAK" << endl;
    else cout << "NIE" << endl;
  }
}

1089. 烽火传递

题目描述

烽火台是重要的军事防御设施，一般建在交通要道或险要处。

一旦有军情发生，则白天用浓烟，晚上有火光传递军情。

在某两个城市之间有 $n$ 座烽火台，每个烽火台发出信号都有一定的代价。

为了使情报准确传递，在连续 $m$ 个烽火台中至少要有一个发出信号。

现在输入 $n,m$ 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。

输入格式

第一行是两个整数 $n,m$ ，具体含义见题目描述；

第二行 $n$ 个整数表示每个烽火台的代价 $a_i$ 。

输出格式

输出仅一个整数，表示最小代价。

数据范围

$1 \le n,m \le 2 \times 10^5$ ,
$0 \le a_i \le 1000$

输入样例：

1 2	5 3 1 2 5 6 2

输出样例：

算法分析

在这里插入图片描述

状态表示： f[i]表示前1~i座烽火台满足条件，且第i座烽火台点燃的方案集合。
属性： 所有符合条件的方案集合中的最小代价值。

状态计算：

如何划分集合？

题目要求在连续 m个烽火台中至少要有一个发出信号，即连续的m个烽火台中至少要有一个被点燃。而f[i]表示的含义中，第i座已经被点燃，因此在第i座向前的前m座烽火台至少要有一个被点燃。被点燃的可以是第 i-m, 第 i-m+1, $\cdots$ ,第i-3,第i-2,第i-1座。

故状态计算方程： f[i] = min(f[j]) + w[i] (i-m<=j<=i-1)

一段区间的最值可以用单调队列求解。此题中，我们定义一个单调递增队列，队列中维护的是f[j]集合。每次拿出队头元素，即长为m的区间中，值最小的f[j]来更新答案。

其实有个小疑问，为什么状态表示时，要将第i座表示为点燃？

我们可以从问题出发，每n座烽火台中必然要有一座要被点燃。那么最后n座烽火台同样也是如此。如果我们将f[i]定义为前1~i座烽火台满足条件，且第i座烽火台点燃的方案集合。那么答案一定在 f[n-m+1],f[n-m+2],,,f[n]之间。也就是说将第i座表示为点燃可以很容易表示出答案。这就给我们一个启发，我们在定义状态表示时，一定要考虑我们定义的状态是否可以包含答案。

最后可以暴力枚举 最终状态 f[i]，其中 $n - m + 1 \le i \le n$

这里可以巧妙利用我们的 滑动窗口

首先我们知道，单调队列 维护的是 $i - m \le j \le i - 1$ 的区间的 $f_j$ 状态最小值

循环迭代完第 $n$ 轮后， $j$ 的范围为 $n - m \le j \le n$

$f[n]$ 进入滑动窗口，但是我们的代码中，判断滑动窗口的大小要在 $n+1$ 轮里进行

所以结束的时候，把滑动窗口往后多划一位，把 $j$ 的范围定在 $n - m + 1 \le j \le n$

则 单调队列 的 队头元素，就是该范围内的 值最小的最终状态，输出 队头元素 即可

Solution

#include <iostream>
using namespace std;

const int N = 2e5 + 10;

int n, m;
int f[N], a[N];
int q[N], hh = 0, tt = -1;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  q[++tt] = 0;
  for (int i = 1; i <= n; ++i) {
    if (hh <= tt && q[hh] < i - m) ++hh;
    f[i] = f[q[hh]] + a[i];
    while (hh <= tt && f[q[tt]] >= f[i]) --tt;
    q[++tt] = i;
  }
  
  //暴力枚举答案
  int ans = 1e9;
  for (int i = n; i >= n - m + 1; --i) ans = min(ans, f[i]);
  //cout << ans;

  //继续利用单调队列滑动窗口
  if (hh <= tt && q[hh] < n - m + 1)  ++hh;
  cout << f[q[hh]];
}

1090. 绿色通道

题目描述

高二数学《绿色通道》总共有 $n$ 道题目要抄，编号 $1,2,…,n$ ，抄第 $i$ 题要花 $a_i$ 分钟。

小 Y 决定只用不超过 $t$ 分钟抄这个，因此必然有空着的题。

每道题要么不写，要么抄完，不能写一半。

下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。

这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。

现在，小 Y 想知道他在这 $t$ 分钟内写哪些题，才能够尽量减轻马老师的怒火。

由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

输入格式

第一行为两个整数 $n,t$ 。

第二行为 $n$ 个整数，依次为 $a_1,a_2,…,a_n$ 。

输出格式

输出一个整数，表示最长的空题段至少有多长。

数据范围

$0 < n \le 5 \times 10^4$ ,
$0 < a_i \le 3000$ ,
$0 < t \le 10^8$

输入样例：

1 2	17 11 6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

输出样例：

算法分析

本题相当于给定我们一个数组a，让我们选出一些数据，让选出的数据和不能超过t，在此前提下，那些没选的数会构成很多连续的段，我们要让这些段的最大值最小。
本题可以使用二分，使用二分的本质是答案具有两段性，假设答案是ans，因为ans是最小的一个，因此小于ans的空题段长度会导致用时超过题目给定的t；大于ans的空题段长度是满足条件的，这是因为允许空的题目长度更长了，用时一定更少了。
我们可以在[0, n]中枚举答案mid，每次检查最大空题段长度不大于mid是否满足题意即可，这样就转化为了1089. 烽火传递。也就是说最多有连续的mid个数可以不被选。

Solution

#include <iostream>
using namespace std;

const int N = 5e4 + 10;

int n, t;
int f[N], a[N];
int q[N], hh = 0, tt = -1;

bool check(int limit) {
  hh = 0, tt = -1;
  q[++tt] = 0;
  for (int i = 1; i <= n; ++i) {
    if (hh <= tt && q[hh] < i - limit - 1) ++hh;
    f[i] = f[q[hh]] + a[i];
    while (hh <= tt && f[q[tt]] >= f[i]) --tt;
    q[++tt] = i;
  }
  
  int minv = 1e9;
  for (int i = n; i >= n - limit; --i) minv = min(minv, f[i]);
  
  return minv <= t;
}


int main() {
  cin >> n >> t;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  int l = 0, r = n;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
  }
  
  cout << l;
}

1091. 理想的正方形

题目描述

有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n \times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入格式

第一行为三个整数，分别表示 $a,b,n$ 的值；

第二行至第 $a+1$ 行每行为 $b$ 个非负整数，表示矩阵中相应位置上的数。

输出格式

输出仅一个整数，为 $a \times b$ 矩阵中所有“ $n \times n$ 正方形区域中的最大整数和最小整数的差值”的最小值。

数据范围

$2 \le a,b \le 1000$ ,
$n \le a,n \le b,n \le 100$ ,
矩阵中的所有数都不超过 $10^9$ 。

输入样例：

输出样例：

算法分析

图中红色阴影格为该行中的最值元素，绿色背影色格为整个矩阵的最值元素。我们可以预处理出每列的行中最值，再对该列求一个最值，就是该子矩阵的最值。

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;

int n, m, k;
int w[N][N];
int rowMax[N][N], rowMin[N][N];
int colMax[N][N], colMin[N][N];
int q[N], hh = 0, tt = -1;

void getMin(int w[], int rowMin[], int r) {
  hh = 0, tt = -1;
  for (int i = 1; i <= r; ++i) {
    if (hh <= tt && q[hh] <= i - k) ++hh;
    while (hh <= tt && w[q[tt]] >= w[i]) --tt;
    q[++tt] = i;
    rowMin[i] = w[q[hh]];
  }
}

void getMax(int w[], int rowMax[], int r) {
  hh = 0, tt = -1;
  for (int i = 1; i <= r; ++i) {
    if (hh <= tt && q[hh] <= i - k) ++hh;
    while (hh <= tt && w[q[tt]] <= w[i]) --tt;
    q[++tt] = i;
    rowMax[i] = w[q[hh]];
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= m; ++j) scanf("%d", &w[i][j]);
  
  for (int i = 1; i <= n; ++i) {
    getMin(w[i], rowMin[i], m);
    getMax(w[i], rowMax[i], m);
  }
  
  int tempMin[N], tempMax[N], ans = 1e9;
  for (int j = k; j <= m; ++j) {
    for (int i = 1; i <= n; ++i) {
      tempMin[i] = rowMin[i][j];
      tempMax[i] = rowMax[i][j];
    }
    getMin(tempMin, colMin[j], n);
    getMax(tempMax, colMax[j], n);
    
    for (int i = k; i <= n; ++i) ans = min(ans, colMax[j][i] - colMin[j][i]);
  }
  
  cout << ans;
}