[luoguP2569] [SCOI2010]股票交易（DP + 单调队列）传送门$f[i][j]$ 表示第i天，手中股票数为j的最优解初始化 $f[i][0]=0$ $0<=i<=n$4种方式转移以前没买过，第i天凭空买 $f[i][j]=j*ap$第i天什么都不干 $f[i][j]=f[i1][j]$第i天

[luoguP2219] [HAOI2007]修筑绿化带（单调队列）传送门需要n*m的算法，考虑单调队列可以预处理出来a[i][j]表示以i,j为右下角的绿化带+花坛的和b[i][j]表示以i,j为右下角的花坛的和那么我们可以单调队列跑出来在AC1,BD1的矩

[POJ3162]Walking Race（DP + 单调队列）传送门

题意：一棵n个节点的树。wc爱跑步，跑n天，第i天从第i个节点开始跑步，每次跑到距第i个节点最远的那个节点（产生了n个距离），现在要在这n个距离里取连续的若干天，使得这些天里最

[TyvjP1313] [NOIP2010初赛]烽火传递（单调队列 + DP）传送门

就是个单调队列+DP嘛。

——代码


1 #include <cstdio>
2
3 const int MAXN = 1000001;
4 int n, m, h = 1, t = 1, ans = ~(1 << 31);
5 int q[MAXN], a[

[luoguP1440] 求m区间内的最小值（单调队列 || 线段树）传送门

这种水题没必要搞线段树了，单调队列就行啊。

——代码


1 #include <cstdio>
2
3 const int MAXN = 2000001;
4 int n, m, h = 1, t = 1;
5 int a[MAXN], q

[luoguP3572] [POI2014]PTA-Little Bird（DP + 单调队列）传送门

DP方程
f[i] = f[j] + (a[j] <= a[i])　　( i k < j < i )
要使 f[i] 最小，需要等号后面的值最小，可以用单调队列来维护。
至于如何维护，具体看代码。

——代码

[luoguP2564] [SCOI2009]生日礼物（队列）传送门

不停的枚举 l ，然后枚举长度，直到所有颜色都包含，这是 n2 做法，超时。
仔细想想，可以用个队列来维护。
还是枚举 l ，用队列来维护当前区间的包含所有颜色，l 增加时再判断

[Vijos1617] 超级教主（DP + 单调队列）传送门

设 f[i] 表示吃完 f[i] 及其以下的能量球后所剩下的能量。
所以 f[i] = max(f[i], f[j] + (sum[i] sum[j]) i * 100) ( 0 <= j < i )
但这是 O(n2) 的，肯定超时，

[luoguP2216] [HAOI2007]理想的正方形（二维单调队列）传送门

1.先弄个单调队列求出每一行的区间为n的最大值最小值。
2.然后再搞个单调队列求1所求出的结果的区间为n的最大值最小值
3.最后扫一遍就行
懒得画图，自己体会吧。

[codevs3622] 假期（单调队列）传送门

首先考虑暴力做法，可以先求一遍前缀和 sum，然后ans = max(ans, sum[i] sum[k]) (i q <= k <= i p)
但这个肯定会超时。
仔细看这个公式，sum[i] 不变，只用求最小 sum

[luoguP2564][SCOI2009]生日礼物（队列）传送门

当然可以用队列来搞啦。


1 # include <iostream>
2 # include <cstdio>
3 # include <cstring>
4 # include <string>
5 # include <cmath>
6 # include <

[luoguP1866]滑动窗口（单调队列）传送门

可以搞2个单调队列。
然后，然后就没有然后了。


1 # include <iostream>
2 # include <cstdio>
3 # include <cstring>
4 # include <string>
5 # include <c