type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于我的个人博客：欢迎大佬们来逛逛
单调队列优化dp的建模形式：这是窗口右滑动的情况
对于窗口左滑动的也是同理。
烽火传递
题目大意：有n个烽火台，在连续的k个烽火台中，至少要有一个发出信号；烽火台发出信号需要消耗代价，问你要使得满足对于所有的烽火台满足条件，最小的代价是多少。
例如：烽火台及其代价如下所示：
1 2 5 6 2 ，其中k=3我们必须选择两个：
- 1 和 5：代价为6
- 1 和 6：代价为7
- …..
- 2 和 2：代价为4，可以得知这是最优解。
因此我们定义 数组 表示当前位置的最小代价值，因此最后的结果就是
其中状态转移可以由前一些位置的最小的值来转移得到：
其中 中的 j 的位置我们可以根据 的值来确定：
这意味如果我们点燃位置为 的烽火台，则必须满足在 位置至少点燃一个烽火台：
因此我们枚举 的位置，对于每一个位置通过单调队列维护前面区间内一个最小值，然后根据上面的状态转移方程转移即可。
本题的单调队列的滑动窗口范围是往右滑动的
修剪草坪
题目大意：在数列中选出长度不超过k的子序列，然后得到每个子序列的和，计算和的最大值，其中元素不能重复选择。
示例给出了：
1 2 3 4 5 ，其中k=2最优解是选择
1 2 和 4 5两个子序列，结果为 12根据贪心的思想，如果我们想要使得最后的和最大， 应该尽量往长了选，则我们假设选择了n个长度为 k 的子序列，则第 k+1 个数字一定不会选，因此我们就可以对这个不会选的数字进行操作。
与其让我们求n个 长度为k 的子序列的和的最大值，不如求在 n个 长度为k+1 的子序列中选择最小值，然后计算他们的和，最后直接用整个数列的和减去由若干最小值组成的和即可。
因此状态转移方程如下：
注意 数组表示的是在 k+1 长度中选择的最小值。
其中 的取值范围是：
本题的单调队列的滑动窗口范围是往右滑动的
绿色通道
题目大意：在规定的时间内做一定数量的题目，做一道题目需要消耗一定的时间。最后使得未做的最长的空题目段的长度最小值，求这个最小值。
根据题目描述的最大值最小，我们很容易想到是二分答案
同时题目告诉你了最长的空题目段越长，马老师越生气，这就是相当于满足了单调性。
因此我们可以二分查找 空题目段的长度，然后选择套用二分查找求最小值的模板即可。
其中我们在二分查找的过程中，假设当前的空题目段长度为 k， 则第 k+1 题目一定不是，因此我们就可以像上一道题目那样，单调队列维护区间最小值。
注意到我们二分的是 k+1 的长度，因此最后我们还需要 -1
琪露诺
题目大意：每次可以走 中的任意一个位置，同时每个位置具有一个值，最后使得走完这 n 个点之后 能够获得的最大值是多少。
很容易可以看出来这道题目是给定区间的单调队列优化 的问题。
状态转移方程与前面都是一样的。
旅行问题
题目大意：n个车站组成一个环，在每个车站有加油量和到下一站的距离，问你从任意的车站出发能够到达最后的终点，即绕一圈。
我们定义 表示为从 i 号车站出发到下一站剩余的流量：
对于环形的问题，我们常常断环成链。
然后计算他们的前缀和：
对于判断 i 号点能否绕一圈，我们可以用
来判断，如果此值大于等于0，则说明 i 号点可以绕一圈，对于 j 我们可以单调队列维护一个最小的 j
同时判断逆时针能够绕一圈，我们可以维护一个后缀和，然后执行相反的操作即可：
此题我们需要同时维护往左滑动的窗口，代表顺时针；和一个维护往右滑动的窗口，代表逆时针。
Watching Fireworks is Fun
题目大意：通过移动位置x使得 来获得最大值
注意到从一个位置到另一个位置可以通过两种方式得到：
窗口向右滑动：
窗口向左滑动：
我们定义 表示当前放的是第 i 次烟花，位置为 j 时的最大权值。
状态转移方程如下：
可以利用滚动数组优化，把数组将为二维。
瑰丽华尔兹
题目大意：往上下左右四个方向移动，每次都可以选择移动或者停止，求最后的最大移动路程
设 表示当前位置为 时的最大移动距离。
我们首先需要枚举四个方向，然后进行求解。
我们先来看往右移动的话：
很容易想到状态转移方程：
即当前点的最大移动距离就等于 点的距离 + 的距离。
因此我们只需要维护一个 的最大值，我们可以使用单调队列进行维护。
这是向右移动的情况，再考虑其他三种情况也是同样的道理。
但是发现一个问题，往右移动， i 是不变的，但是往下移动的时候，j 又是不变的，我们很难用 来具体的表示四个方向，因此我们抽象为：
其中 就是转移之前的最大移动距离， 表示的就是转移之前的那个位置。
因此我们对于四种方向的枚举就可以实现了：
其中 函数就是我们维护单个方向滑动窗口最大值的函数：
- x和y：每个方向的起始位置
- L：表示最多在这个方向移动L距离
- time：表示时间间隔。
- d：表示方向，用于移动。
我们在此函数中利用滑动窗口维护一个最大值即可，注意当碰到障碍的时候，我们的窗口清零。
股票交易
题目大意：在某天可以选择买入股票，卖出股票，其中买入和卖出都有数量限制，并且也具有最大持股数限制，并且还具有时间间隔限制，求得最后能获得的最大利润。
定义 表示第 天持股 数量的最大利润。
我们可以分成四种情况讨论：
- 只买入：
- 不买不卖：
- 在之前某天的基础上买入：
- 其中 的取值范围： 表示全买或者一个都不买
- 在之前某天的基础上卖出：
- 其中 的取值范围： 表示一个都不卖或者全卖
因此我们便可以使用单调队列维护窗口的最大值了。
其中 便是我们需要维护的值。
注意窗口的移动情况：
- 买入：窗口往右滑，顺序遍历
- 卖出：窗口往左滑，逆序遍历
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/45ac4219-bc2e-49fe-b1e5-f8207980f4f2
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。