前言
这已经是很基础很模板化的优化了，我们可以理解为用贪心的思路去掉了永远不可能用到的状态，通常用于长度固定是个区间、最大值且满足单调性的题目。
如果一个选手比你小，还比你强，你就永远也打不过他了。这很残酷但这也是单调队列的思想，虽然现实情况比较多变。
P3572 [POI2014] PTA-Little Bird
最基础的单调队列优化题，我们暴力写出后得到：
\[f_i=\min f_k(+1(a_i>=a_k)) \ \ \ \ \ k\in [i-1,i-k] \]我们发现这个 \(\min\) 就是满足单调性的条件，而且如果 \(f\) 值相同时我们再对比 \(a\) 的大小，将 \(a\) 更大的留下，这个过程就相当于一个排序的过程，只不过因为单调性所以我们删掉一些数也没关系。
满足单调性的条件不止有一个，所以条件都满足单调性就尽管单调队列优化。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define re register
#define ll long long
const int N=1e6+10;
const int mod=998244353;
using namespace std;
int n,q;
int a[N];
int f[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>q;
while(q--){
int k;
cin>>k;
memset(f,0x3f,sizeof f);
f[1]=0;
for(int i=2;i<=n;i++){
for(int j=i-1;j>=max(1ll,i-k);j--){
if(a[j]>a[i]){
f[i]=min(f[i],f[j]);
}
else{
f[i]=min(f[i],f[j]+1);
}
}
}
cout<<f[n]<<"\n";
}
return 0;
}
P1725 琪露诺
终于自己写出来的题，但确实很简单，暴力都能80分。
暴力：每个位置可以从区间 \([i-r,i-l]\) 转移过来，那就直接转移。
正解：可以发现这个区间长度是固定的，每次取出区间内的最大值转移过来，可以用滑动区间的方法维护区间值，然后就可以了。
好吧好吧还是放一下吧，点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
int n,l,r;
int a[N];
int f[N];
queue<int> q;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(f,-0x3f,sizeof f);
cin>>n>>l>>r;
n++;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=-1e9;
f[1]=a[1];
for(int i=1;i<=n+1000;i++){
if(!q.empty()&&q.front()<=i-l-(r-l+1)){
q.pop();
}
while(!q.empty()&&f[q.front()]<f[i-l]){
q.pop();
}
if(i-l>=1){
q.push(i-l);
int k=q.front();
int x=f[q.front()];
f[i]=max(f[i],a[i]+x);
}
if(i>=n+1){
ans=max(ans,f[i]);
}
}
cout<<ans;
return 0;
}
P1714 切蛋糕
我会暴力，枚举位置，向后加和，复杂度 \(O(n^2)\) 太差了。
因为要求区间和最大，所以考虑维护一个前缀和，每次找到前长度m的区间内的最小值转移过来，但要用双端队列维护，如这个样例 [3,-2,4,-1,-5] 一开始要先push(0)吧，后面的前缀和都比0大所以都会堆积在最后，但当0自然弹出时，后面的数并没有降序排序，因为我们会只看sum_0来弹出而又没有比他小的，然后就寄了。
后记：才发现用queue维护都是不对的，希望以后长记性。
确实该注意
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
#define int ll
int n,m;
int a[N];
int sum[N];
int f[N];
int ans=-1e9;
list<int> q;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
memset(f,-0x3f,sizeof f);
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
q.push_back(0);
for(int i=1;i<=n;i++){
while(!q.empty()&&q.front()<i-m){
q.pop_front();
}
f[i]=max(f[i],sum[i]-sum[q.front()]);
ans=max(ans,f[i]);
while(!q.empty()&&sum[q.back()]>=sum[i]){
q.pop_back();
}
q.push_back(i);
}
cout<<ans;
return 0;
}
P2627 [USACO11OPEN] Mowing the Lawn G
我会暴力，枚举位置i，枚举长度j，枚举之前位置k，目前连续与之前最大连续转移过来。
优化暴力，每个奶牛只有选和不选两个状态，那直接dp这个状态，然后分类转移（\(f[i][0]\) 不选这个奶牛最大的值）。
-
\(f[i][0]=max(f[i-1][0],f[i-1][1])\)
-
\(f[i][1]=max(f[i][1],f[j-1][0]+sum[i]-sum[j]),[max(i-m,0)<=j<i]\)
然后可以愉快转移了。
可以发现下面的枚举j是是一个区间内找到最大的值，明锐察觉可以单调队列优化，好！！结束了（维护这个 \(ans=max(ans,f[j][0]-sum[j])\)）。
P2629 好消息，坏消息
很离谱的一道题，我想不出来也很正常吧（逃ε=ε=ε=┏(゜ロ゜;)┛）其实想出来一点了，但假了一半，然后就无法思考了，开摆。
暴力：\(O(n^2)\) 枚举判断，竟然能得85！！！
正解：因为是环，可以拆成链，此时可以这么看数组 -3,5,1,2,-3,5,1 每个区间对于这一种情况，像 [1,2,-3,5] 对应 1->2->-3->5，然后此时计算一个区间可以用前缀和，第k个区间，找到区间内前缀和的最小值减去 \(sum[k-1]\) （因为和此时的区间没关系，我们要找到依次加和过程中的最小值）判断是否为负数，统计答案即可，找到区间前缀和最小就可以用单调队列实现。
标签：队列,sum,cin,long,int,dp,区间,单调 From： https://www.cnblogs.com/sadlin/p/18544028