本系列是这本算法教材的扩展资料：《算法竞赛入门到进阶》(京东 当当 ) 清华大学出版社
如有建议，请联系：（1）QQ 群，567554289；（2）作者QQ，15512356
文章目录
单调队列是很常见的DP优化技术，本节讲解基本的思路和方法。在前面一篇博文“斜率优化”中，单调队列也有关键的应用。
1. 单调队列优化的原理
先回顾单调队列的概念，它有以下特征：
（1）单调队列的实现。用双端队列实现，队头和队尾都能插入和弹出。手写双端队列很简单。
（2）单调队列的单调性。队列内的元素具有单调性，从小到大，或者从大到小。
（3）单调队列的维护。每个新元素都能进入队列，它从队尾进入队列时，为维护队列的单调性，应该与队尾比较，把破坏单调性的队尾弹出。例如一个从小到大的单调队列，如果要进队的新元素a比原队尾v小，那么把v弹走，然后a继续与新的队尾比较，直到a比队尾大为止，最后a进队尾。
单调队列在DP优化中的基本应用，是对这样一类DP方程进行优化：
d p [ i ] = m i n { d p [ j ] + a [ i ] + b [ j ] } dp[i] = min\{dp[j] + a[i] + b[j]\} dp[i]=min{dp[j]+a[i]+b[j]} L ( i ) ≤ j ≤ R ( i ) L(i) ≤ j ≤ R(i) L(i)≤j≤R(i) --方程(1)
公式中的 m i n min min也可以是 m a x max max。方程的特点是其中关于 i i i的项 a [ i ] a[i] a[i]和关于 j j j的项 b [ j ] b[j] b[j]是独立的。 j j j被限制在窗口 [ L ( i ) , R ( i ) ] [L(i), R(i)] [L(i),R(i)]内，常见的例如给定一个窗口值 k k k， i − k ≤ j ≤ i i-k≤j≤i i−k≤j≤i。这个DP方程的编程实现，如果简单地对i做外层循环，对j做内层循环，复杂度 O ( n 2 ) O(n^2) O(n2)。如果用单调队列优化，复杂度可提高到 O ( n ) O(n) O(n)。
为什么单调队列能优化这个DP方程？
概况地说，单调队列优化算法能把内外i、j两层循环，精简到一层循环。其本质原因是“外层 i i i变化时，不同的 i i i所对应的内层 j j j的窗口有重叠”。如下图所示， i = i 1 i=i_1 i=i1时，对应的 j 1 j_1 j1的移动窗口（窗口内处理DP决策）范围是上面的阴影部分； i = i 2 i=i_2 i=i2时，对应的 j 2 j_2 j2处理的移动窗口范围是下面的阴影；两部分有重叠。当 i i i从 i 1 i_1 i1增加到 i 2 i_2 i2时，这些重叠的部分被重复计算，如果减少这些重复，就得到了优化。
图1 外层i和内层j的循环
在窗口内处理的这些决策，有两种情况：
（1）被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。
（2）未被排除的决策。内层j未排除的决策，在外层i增大时，仍然能按原来的顺序被用到。
那么可以用单调队列统一处理这些决策，从而精简到只用一个循环，得到优化。下面详细介绍单调队列的操作。
（1）求一个dp[i]。i是外层循环，j是内层循环，在做j的内层循环时，可以把外层的i看成一个定值。此时a[i]可以看成常量，把j看成窗口[L(i), R(i)]内的变量，DP方程(1)等价于：
d p [ i ] = m i n { d p [ j ] + b [ j ] } + a [ i ] dp[i] = min\{dp[j] + b[j]\} + a[i] dp[i]=min{dp[j]+b[j]}+a[i]
问题转化为求窗口 [ L ( i ) , R ( i ) ] [L(i), R(i)] [L(i),R(i)]内的最优值 m i n { d p [ j ] + b [ j ] } min\{dp[j] + b[j]\} min{dp[j]+b[j]}。记 d s [ j ] = d p [ j ] + b [ j ] ds[j] = dp[j] + b[j] ds[j]=dp[j]+b[j],在窗口内，用单调队列处理 d s [ j ] ds[j] ds[j]，排除掉不合格的决策，最后求得区间内的最优值，最优值即队首。得到窗口内的最优值后，就可以求得 d p [ i ] dp[i] dp[i]。另外，队列中留下的决策，在 i i i变化后仍然有用。
请注意，队列处理的决策 d s [ j ] ds[j] ds[j]只和 j j j有关，和 i i i无关，这是本优化方法的关键。如果既和 i i i有关，又和 j j j有关，它就不能在下一步“（2）求所有的dp[i]”时得到应用。具体来说是这样的：1）如果 d s [ j ] ds[j] ds[j]只和 j j j有关，那么一个较小的 i 1 i_1 i1操作的某个策略 d s [ j ] ds[j] ds[j]，和一个较大的 i 2 i_2 i2所操作的某个策略 d s [ j ] ds[j] ds[j]是相等的，从而产生了重复性，可以优化；2）如果 d s [ ] ds[] ds[]和 i i i、 j j j都有关，那么就没有重复性，无法优化。请结合后面的例题深入理解。
（2）求所有的 d p [ i ] dp[i] dp[i]。考虑外层循环i变化时的优化方法。一个较小的 i 1 i_1 i1所排除的 d s [ j ] ds[j] ds[j]，在处理一个较大的 i 2 i_2 i2时，也会被排除，重复排除其实没有必要；一个较小的 i 1 i_1 i1所得到的决策，仍能用于一个较大的 i 2 i_2 i2。统一用一个单调队列处理所有的 i i i，每个 d s [ j ] ds[j] ds[j]（提示：此时 j j j不再局限于窗口 [ L ( i ) , R ( i ) ] [L(i), R(i)] [L(i),R(i)]，而是整个区间 1 ≤ j ≤ n 1≤j≤n 1≤j≤n，那么 d s [ j ] ds[j] ds[j]实际上就是 d s [ i ] ds[i] ds[i]了)都进入队列一次，并且只进入队列一次，总复杂度 O ( n ) O(n) O(n)。此时内外层循环 i i i、 j j j精简为一个循环 i i i。
下面的例题(1)是以上原理的模板题。例题(2)“多重背包”是一个较难的例子，通过它能更透彻地理解单调队列优化的实质。
2. 例题（1）洛谷P2627
Mowing the Lawn https://www.luogu.com.cn/problem/P2627
有一个包括n个正整数的序列，第i个整数是Ei，给定一个整数k，找这样的子序列，子序列中的数在原序列连续的不能超过k个。对子序列求和，问所有子序列中最大的和是多少。1 ≤ n ≤ 100,000，0 ≤ Ei ≤ 1,000,000,000，1 ≤ k ≤ n。
例如n = 5，{7, 2, 3, 4, 5}，k = 2，子序列{7, 2, 4, 5}有最大和18，其中的连续部分是{7,2}、{4,5}，长度都不超过k = 2。
由于 n n n较大，算法的复杂度应该小于 O ( n 2 ) O(n^2) O(n2)，否则会超时。
用DP解题，定义 d p [ i ] dp[i] dp[i]为前 i i i头奶牛的最大子序列和，状态转移方程是：
d p [ i ] = m a x { d p [ j − 1 ] + s u m [ i ] − s u m [ j ] } dp[i]= max\{dp[j-1] + sum[i] - sum[j]\} dp[i]=max{dp[j−1]+sum[i]−sum[j]} i − k ≤ j ≤ i i-k≤j≤i i−k≤j≤i
其中 s u m [ i ] sum[i] sum[i]是前缀和，即从 E 1 E_1 E1 加到 E i E_i Ei。
方程符合单调队列优化的标准方程： d p [ i ] = m i n { d p [ j ] + b [ j ] } + a [ i ] dp[i] = min\{dp[j] + b[j]\} + a[i] dp[i]=min{dp[j]+b[j]}+a[i]。下面用这个例子详细讲解单调优化队列的操作过程。
把 i i i看成定值，上述方程等价于下面的方程：
d p [ i ] = m a x { d p [ j − 1 ] − s u m [ j ] } + s u m [ i ] dp[i]= max\{dp[j-1] - sum[j]\} + sum[i] dp[i]=max{dp[j−1]−sum[j]}+sum[i] i − k ≤ j ≤ i i-k≤j≤i i−k≤j≤i
求 d p [ i ] dp[i] dp[i]，就是找到一个决策 j j j， i − k ≤ j ≤ i i-k≤j≤i i−k≤j≤i，使得 d p [ j − 1 ] − s u m [ j ] dp[j-1] - sum[j] dp[j−1]−sum[j]最大。
对这个方程编程求解，如果简单地做 i i i、 j j j的循环，复杂度是 O ( n k ) O(nk) O(nk)的，约等于 O ( n 2 ) O(n^2) O(n2)。
如何优化？回顾单调队列优化的实质：“外层 i i i变化时，不同的 i i i所对应的内层j的窗口有重叠”。
内层 j j j所处理的决策 d p [ j − 1 ] − s u m [ j ] dp[j-1] - sum[j] dp[j−1]−sum[j]，在 i i i变化时，确实发生了重叠。下面推理如何使用单调队列。
首先，对一个固定的 i i i，用一个递减的单调队列求最大的 d p [ j − 1 ] − s u m [ j ] dp[j-1] - sum[j] dp[j−1]−sum[j]。记 d s [ j ] = d p [ j − 1 ] − S u m [ j ] ds[j] = dp[j-1] - Sum[j] ds[j]=dp[j−1]−Sum[j]，并记这个 i i i对应的最大值为 d s m a x [ i ] = m a x { d s [ j ] } dsmax[i]= max\{ds[j]\} dsmax[i]=max{ds[j]}。用单调队列求 d s m a x [ i ] dsmax[i] dsmax[i]的步骤见下面的说明。
（1）设从 j = 1 j = 1 j=1开始，首先让 d s [ 1 ] ds[1] ds[1]进队列。此时窗口内的最大值 d s m a x [ i ] = d s [ 1 ] dsmax[i] = ds[1] dsmax[i]=ds[1]。
（2） j = 2 j = 2 j=2， d s [ 2 ] ds[2] ds[2]进队列，讨论两种情况：
1）若 d s [ 2 ] ≥ d s [ 1 ] ds[2] ≥ ds[1] ds[2]≥ds[1], 说明 d s [ 2 ] ds[2] ds[2]更优，弹走 d s [ 1 ] ds[1] ds[1]， d s [ 2 ] ds[2] ds[2]进队成为新队头，更新 d s m a x [ i ] = d s [ 2 ] dsmax[i] = ds[2] dsmax[i]=ds[2]。这一步排除了不好的决策，留下更好的决策。
2）若 d s [ 2 ] < d s [ 1 ] ds[2] < ds[1] ds[2]<ds[1], d s [ 2 ] ds[2] ds[2]进队列。队头仍然是 d s [ 1 ] ds[1] ds[1]，保持 d s m a x [ i ] = d s [ 1 ] dsmax[i] = ds[1] dsmax[i]=ds[1]。
这2种情况下 d s [ 2 ] ds[2] ds[2]都进队，是因为 d s [ 2 ] ds[2] ds[2]比 d s [ 1 ] ds[1] ds[1]更晚于离开窗口范围k，即存活时间更长。
（3）继续以上操作，让窗口内的每个 j j j， i − k ≤ j ≤ i i-k≤j≤i i−k≤j≤i，都有机会进队，并保持队列是从大到小的单调队列。
经过以上步骤，求得了固定一个 i i i时的最大值 d s m a x [ i ] dsmax[i] dsmax[i]。
当i变化时，统一用一个单调队列处理，因为一个较小的 i 1 i_1 i1所排除的 d s [ j ] ds[j] ds[j]，在处理后面较大的 i 2 i_2 i2时，也会被排除，没有必要再重新排除一次；而且较小的 i 1 i_1 i1所得到的队列，后面较大的 i 2 i_2 i2也仍然有用。这样，每个 d s [ j ] （ 1 ≤ j ≤ n ) ds[j]（1≤j≤n) ds[j]（1≤j≤n)都有机会进入队列一次，并且只进入队列一次，总复杂度 O ( n ) O(n) O(n)。
如果对上述解释仍有疑问，请仔细分析洛谷P2627的代码1。注意一个小技巧：虽然理论上在队列中处理的决策是 d p [ j − 1 ] − s u m [ j ] dp[j-1] - sum[j] dp[j−1]−sum[j]，但是在编码时不用这么麻烦，队列只需要记录 j j j，然后在判断的时候用 d p [ j − 1 ] − s u m [ j ] dp[j-1] - sum[j] dp[j−1]−sum[j]进行计算即可。
代码中去头和去尾的2个while语句是单调队列的常用写法，可以看作单调队列的特征。
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long n,k,e[maxn],sum[maxn],dp[maxn];
long long ds[maxn]; //ds[j] = dp[j-1]-sum[j]
int q[maxn],head=0,tail=1; //递减的单调队列，队头最大
long long que_max(int j){
ds[j] = dp[j-1]-sum[j];
while(head<=tail && ds[q[tail]]<ds[j]) //去掉不合格的队尾
tail--;
q[++tail]=j; //j进队尾
while(head<=tail && q[head]<j-k) //去掉超过窗口k的队头
head++;
return ds[q[head]]; //返回队头，即最大的dp[j-1]-sum[j]
}
int main(){
cin >> n >> k; sum[0] = 0;
for(int i=1;i<=n;i++){
cin >> e[i];
sum[i] = sum[i-1] + e[i]; //计算前缀和
}
for(int i=1;i<=n;i++)
dp[i] = que_max(i) + sum[i]; //状态转移方程
cout << dp[n];
}
3. 例题（2）多重背包
本文给出多重背包的3种解法：朴素方法、二进制拆分优化、单调队列优化。
多重背包问题：给定 n n n种物品和一个背包，第 i i i种物品的体积是 w i w_i wi，价值为 v i v_i vi，并且有 m i m_i mi个，背包的总容量为 W W W。如何选择装入背包的物品，使得装入背包中的物品的总价值最大?
洛谷 P1776 宝物筛选 https://www.luogu.com.cn/problem/P1776
输入：
第一行是整数 n n n 和 W W W，分别表示物品种数和背包的最大容量。
接下来 n n n 行，每行三个整数 v i v_i vi、 w i w_i wi、 m i m_i mi，分别表示第 i i i个物品的价值、体积、数量。
输出：
输出一个整数，表示背包不超载的情况下装入物品的最大价值。
解法(1): 朴素方法
给出两种思路。
第一种思路，转换为0/1背包问题。把相同的 m i m_i mi个第 i i i种物品看成独立的 m i m_i mi个，总共 ∑ i = 1 n m i \sum_{i=1}^nm_i ∑i=1nmi个物品，然后按0/1背包求解，复杂度是 O ( W × ∑ i = 1 n m i ) O(W\times\sum_{i=1}^nm_i) O(W×∑i=1nmi)。
第二种思路，直接求解。定义状态 d p [ i ] [ j ] dp[i][j] dp[i][j]：表示把前 i i i个物品装进容量 j j j的背包，能装进背包的最大价值。第 i i i个物品分为装或不装两种情况，得到多重背包的状态转移方程：
d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − k ∗ w [ i ] ] + k ∗ v [ i ] } dp[i][j] = max\{dp[i-1][j], dp[i-1][j-k*w[i]] + k*v[i]\} dp[i][j]=max{dp[i−1][j],dp[i−1][j−k∗w[i]]+k∗v[i]} 1 ≤ k ≤ m i n { m [ i ] , j / w [ i ] } 1≤k≤min\{m[i], j/w[i]\} 1≤k≤min{m[i],j/w[i]}
直接写 i 、 j 、 k i、j、k i、j、k三重循环，复杂度和第一种思路的复杂度一样。下面用滚动数组编码，提交判题后会超时。
#include <bits/stdc++.h>
using namespace std;
const int MAXX=100010;
int n,W,dp[MAXX];
int v[MAXX],w[MAXX],m[MAXX]; //物品i的价值、体积、数量
int main(){
cin >> n >> W; //物品数量，背包容量
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>m[i];
//以下是滚动数组版本的多重背包
for(int i=1;i<=n;i++) //枚举物品
for(int j=W;j>=w[i];j--) //枚举背包容量
for(int k=1; k<=m[i] && k*w[i]<=j; k++)
dp[j] = max(dp[j],dp[j-k*w[i]]+k*v[i]);
cout << dp[W] << endl;
return 0;
}
解法(2): “二进制拆分”优化
这是一种简单而有效的技巧，请读者掌握。在解法（1）的基础上加上这个优化，能显著改善复杂度。原理很简单，例如第 i i i种物品有 m i m_i mi=25个，这25个物品放进背包的组合，有0~25的26种情况。不过要组合成26种情况，其实并不需要25个物品。根据二进制的计算原理，任何一个十进制整数 X X X，都可以用1、2、4、8…这些2的倍数相加得到，例如21 = 16 + 4 + 1，这些2的倍数只有 l o g 2 X log_2X log2X个。题目中第 i i i种物品有 m i m_i mi个，用 l o g 2 m i log_2m_i log2mi个数就能组合出0~ m i m_i mi种情况。总复杂度从 O ( W × ∑ i = 1 n m i ) O(W\times\sum_{i=1}^nm_i) O(W×∑i=1nmi)优化到了 O ( W × ∑ i = 1 n l o g 2 m i ) O(W\times\sum_{i=1}^nlog_2m_i) O(W×∑i=1nlog2mi)，已经足够好了。
注意具体拆分的方法，先按2的倍数从小到大拆，最后加上一个小于最大倍数的余数。例如一个物品数量是21个，把它拆成1、2、4、8、6这5个“新物品”，最后的余数是6，6<16= 2 4 2^4 24，读者可以验证用这5个数能组合成1~21内的所有数字。再例如30，拆成1、2、4、8、15，余数15<16= 2 4 2^4 24。
#include <bits/stdc++.h>
using namespace std;
const int MAXX=100010;
int n,W,dp[MAXX];
int v[MAXX],w[MAXX],m[MAXX];
int new_n; //二进制拆分后的新物品总数量
int new_v[MAXX],new_w[MAXX],new_m[MAXX]; //二进制拆分后新物品
int main(){
cin >> n >>W;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>m[i];
//以下是二进制拆分
int new_n = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m[i];j<<=1) { //二进制枚举：1,2,4...
m[i]-=j; //减去已拆分的
new_w[++new_n] = j*w[i]; //新物品
new_v[new_n] = j*v[i];
}
if(m[i]){ //最后一个是余数
new_w[++new_n] = m[i]*w[i];
new_v[new_n] = m[i]*v[i];
}
}
//以下是滚动数组版本的0/1背包
for(int i=1;i<=new_n;i++) //枚举物品
for(int j=W;j>=new_w[i];j--) //枚举背包容量
dp[j]=max(dp[j],dp[j-new_w[i]]+new_v[i]);
cout << dp[W] << endl;
return 0;
}
解法(3): 单调队列优化
用单调队列优化求解多重背包，复杂度是O(nW)，是最优的算法。
回顾解法(1)用滚动数组实现的多重背包程序：
for(int i=1;i<=n;i++) //枚举每个物品
for(int j=W;j>=w[i];j--) //枚举背包容量
for(int k=1; k<=m[i] && k*w[i]<=j; k++)
dp[j] = max(dp[j],dp[j-k*w[i]]+k*v[i]);
状态转移方程是： d p [ j ] = m a x { d p [ j − k w i ] + k v i } dp[j] = max\{dp[j - kw_i] + kv_i\} dp[j]=max{dp[j−kwi]+kvi} 1 ≤ k ≤ m i n { m i , j / w i } 1≤k≤min\{m_i, j/w_i\} 1≤k≤min{mi,j/wi}
程序是 i 、 j 、 k i、j、k i、j、k的三重循环。其中循环 i 、 j i、j i、j互相独立，没有关系，不能优化。循环 j 、 k j、k j、k是相关的， k k k在 j j j上有滑动窗口，所以目标是优化 j 、 k j、k j、k这两层循环，此时可以把与 i i i有关的部分看成定值。
对比单调队列的模板方程： d p [ i ] = m a x { d p [ j ] + a [ i ] + b [ j ] } dp[i] = max\{dp[j] + a[i] + b[j]\} dp[i]=max{dp[j]+a[i]+b[j]}
相差太大，似乎并不能应用单调队列。
回顾单调队列优化的实质，“外层 i i i变化时，不同的i所对应的内层 j j j的窗口有重叠”。状态方程 d p [ j ] = m a x { d p [ j − k w i ] + k v i } dp[j] = max\{dp[j - kw_i] + kv_i\} dp[j]=max{dp[j−kwi]+kvi}的外层是 j j j，内层是 k k k， k k k的滑动窗口是否重叠？下面观察 j − k w i j - kw_i j−kwi的变化情况。首先对比外层 j j j和 j + 1 j+1 j+1，让 k k k从 1 1 1递增，它们的 j − k w i j - kw_i j−kwi等于：
| j: | j-3w | j-2w | j-w | ||||||
| j+1: | j+1-3w | j+1-2w | j-w |
没有发生重叠。但是如果对比 j j j和 j + w i j + w_i j+wi：
| j: | j-3w | j-2w | j-w | ||||||
| j: | j+w-4w | j+w-3w | j+w-2w |
发生了重叠。
可以推理出当 j j j等于 j j j、 j + w i j+w_i j+wi、 j + 2 w i j+2w_i j+2wi、…时有重叠，进一步推理出：当 j j j除以 w i w_i wi的余数相等时，这些 j j j对应的内层 k k k发生重叠。那么，如果把外层 j j j的循环，改成按 j j j除以 w i w_i wi的余数相等的值进行循环，就能利用单调队列优化了。
下面把原状态方程变换为可以应用单调队列的模板方程。
原方程是：
d p [ j ] = m a x { d p [ j − k w i ] + k v i } dp[j] = max\{dp[j - kw_i] + kv_i\} dp[j]=max{dp[j−kwi]+kvi} 1 ≤ k ≤ m i n { m i , j / w i } 1≤k≤min\{m_i, j/w_i\} 1≤k≤min{mi,j/wi} --方程(2)
令 j = b + y w i j = b + yw_i j=b+ywi，其中 b = j b = j%w_i b=j， b b b为 j j j除以 w i w_i wi得到的余数； y = j / w i y = j/w_i y=j/wi， y y y是 j j j整除 w i w_i wi的结果。
把 j j j代入方程(2)，得2：
d p [ b + y w i ] = m a x { d p [ b + ( y − k ) w i ] + k v i } dp[b + yw_i] = max\{dp[b + (y-k)w_i] + kv_i\} dp[b+ywi]=max{dp[b+(y−k)wi]+kvi} 1 ≤ k ≤ m i n { m i , y } 1≤k≤min\{m_i, y\} 1≤k≤min{mi,y}
令 x = y − k x = y-k x=y−k，代入上式得：
d p [ b + y w i ] = m a x { d p [ b + x w i ] − x v i + y v i } dp[b + yw_i] = max\{dp[b + xw_i] - xv_i + yv_i\} dp[b+ywi]=max{dp[b+xwi]−xvi+yvi} y − m i n ( m i , y ) ≤ x ≤ y y-min(m_i,y)≤x≤y y−min(mi,y)≤x≤y
与模板方程 d p [ i ] = m i n { d p [ j ] + a [ i ] + b [ j ] } dp[i] = min\{dp[j] + a[i] + b[j]\} dp[i]=min{dp[j]+a[i]+b[j]}对比，几乎一样。
用单调队列处理 d p [ b + x w i ] − x v i dp[b + xw_i] - xv_i dp[b+xwi]−xvi，下面给出代码，上述推理过程，详见代码中的注释。
#include<bits/stdc++.h>
using namespace std;
const int MAXX=100010;
int n,W;
int dp[MAXX],q[MAXX],num[MAXX];
int w,v,m; //物品的价值v、体积w、数量m
int main(){
cin >> n >> W; //物品数量n，背包容量W
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
cin>>v>>w>>m; //物品i的价值v、体积w、数量m
if(m>W/w) m = W/w; //计算 min{m, j/w}
for(int b=0;b<w;b++){ //按余数b进行循环
int head=1, tail=1;
for(int y=0;y<=(W-b)/w;y++){ //y = j/w
int tmp = dp[b+y*w]-y*v; //用队列处理tmp = dp[b + xw] - xv
while(head<tail && q[tail-1]<=tmp) tail--;
q[tail] = tmp;
num[tail++] = y;
while(head<tail && y-num[head]>m) head++; // 约束条件 y-min(mi,y)≤x≤y
dp[b+y*w] = max(dp[b+y*w],q[head]+y*v); // 计算新的dp[]
}
}
}
cout << dp[W] << endl;
return 0;
}
算法的复杂度：外层 i i i循环 n n n次，内层的 b b b和 y y y循环总次数是 w × ( W − b ) / w ≈ W w×(W-b)/w≈W w×(W−b)/w≈W，且每次只进出队列一次，所以总复杂度是 O ( n W ) O(nW) O(nW)。
4. 习题
洛谷 P1725，P3957
poj 1821，2373，3017，3926
hdu 3401，3514，5945
改写自：https://www.luogu.com.cn/blog/user21293/solution-p2627 ↩︎
参考：https://blog.csdn.net/qq_40679299/article/details/81978770。 ↩︎
