单调队列总结
前言
单调队列易于理解，这里不多说实现了，只说一些例题和用途
单调队列实质是O（n）求一段序列中多段有相同长度限制的子序列的最值
裸体裸题：
1.滑动窗口：板子
2.理想正方形 ：（其实也是板子）每一横行用维护单调队列维护，称为q1，再用另一组单调队列维护一列，称为q2，q2内元素为q1队首
3.修筑绿化带：与上一题目差别不大，先预处理出以x,y为右下角的C*D矩阵的和，记作d[ i ][ j ]，然后在枚举A*B矩阵右下角，在（A-2）*（B-2）内部单调队列取d[ i ][ j ]最值，边界有点恶心
优化DP：
题目概述：你有无限的本金，你要炒股（我也不知道为啥
每天股票买入为 APi，卖出价为BPi，每天最多买ASi股，最多卖BSi股，每次操作后（买入卖出均算操作）需隔w天进行下次操作（会累的嘛）,你手里股票不能超过MAXP股，求T天后的最大收益。
考虑暴力DP：
f[ i ][ j ]为到第i天手里有j股的最大收益；
1.凭空买入 f[ i ][ j ]= -APi * j （j <= ASi ）；
2.摸鱼（啥也不干）f[ i ][ j ] = max（f[ i ][ j ] ，f[ i-1 ][ j ]）；
3.从以前买/卖 考虑到上一步，我们已经把第i天之前的最优解转移到第i天了，所以我们直接取f[ i-w-1 ][ j ]进行操作一定是最优的
看到这里暴力DP您一定会写了QAQ
考虑单调队列优化：
我们发现第三步的转移方程是O（n^2）级别的，外面再套个天数就是N^3了，TLE；
列出第三步的买入方程：
f[ i ][ j ] = max｛f[ i ][ j ]，f[ i-w-1 ][ j-k ] - k*APi｝（0<k<=ASi）；
略作转化，将（j-k）设为 k，则方程变为
f[ i ][ j ] = max ｛f[ i-w-1 ][ k ] + k*APi - j*APi｝（j-ASi<=k< j）；
将 j*APi 提出
f[ i ][ j ] = max ｛f[ i-w-1 ][ k ] + k*APi ｝- j*APi（j-ASi<=k< j）；
我们发现问题变为了求 [ j-ASi，j）这段区间内 f[ i-w-1 ][ k ] + k*APi 的最大值，可以用单调队列优化
买入操作类似，不推了（懒
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,w,ans;
struct point
{
int ap,bp,as,bs;
}g[2010];
int f[2010][2010];
int q[2010][2];
int head,tail;
signed main()
{
n=read(),m=read(),w=read();
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=n;++i)
{
g[i].ap=read(),g[i].bp=read(),g[i].as=read(),g[i].bs=read();
f[i][0]=0;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=g[i].as;++j) f[i][j]=-j*g[i].ap;
for(int j=0;j<=m;++j) f[i][j]=max(f[i][j],f[i-1][j]);
head=0,tail=-1;
if(i<=w) continue;
for(int j=0;j<=m;++j)
{
while(q[head][0]<j-g[i].as&&head<=tail) ++head;
while(f[i-w-1][j]+j*g[i].ap>=q[tail][1]&&head<=tail) --tail;
q[++tail][0]=j;
q[tail][1]=f[i-w-1][j]+j*g[i].ap;
if(head<=tail) f[i][j]=max(f[i][j],q[head][1]-j*g[i].ap);
}
head=0,tail=-1;
for(int j=m;j>=0;--j)
{
while(q[head][0]>j+g[i].bs&&head<=tail) ++head;
while(f[i-w-1][j]+j*g[i].bp>=q[tail][1]&&head<=tail) --tail;
q[++tail][0]=j;
q[tail][1]=f[i-w-1][j]+j*g[i].bp;
if(head<=tail) f[i][j]=max(f[i][j],q[head][1]-j*g[i].bp);
}
for(int j=0;j<=m;++j) ans=max(ans,f[i][j]);
}
printf("%d
",ans);
return 0;
}
瑰丽华尔兹
题目概述：在n*m网格上有个人，初始在（x，y）点，K次输入，每次给出st，ed，和d，他在st到ed时间段内每秒可以朝着d方向走一格或不走，地图上有一些障碍，人不能碰到障碍或走出地图，请问这个人最后最多走多少格；
暴力DP：
设f[ t ][ i ][ j ]为在第t次给出后在（i，j）处最多走了多少格
每次给出st，ed，和 d 后循环每个节点，直接在每个节点模拟
复杂度O（K*N*M*T）；
加个滚动数组优化你A了（？）
本着严谨的态度我们还是谈一下单调队列优化：
令ed=ed-st+1；
继续枚举（i，j），问题为在（i，j）处从某一距离不超过ed方向转移过来的最大值，符合单调队列本质
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,x,y,k,ans;
int a[210][210];
char ch;
int f[2][210][210];
int t,tx,ty,st,ed,d;
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
int q[210][2];
int head,tail;
inline void work1(int y)
{
for(int x=n+1;x>=1;--x)
{
if(!a[x][y])
{
head=0,tail=-1;
continue;
}
while(q[head][0]-x>ed&&head<=tail) ++head;
while(f[t^1][x][y]+x>=q[tail][1]&&head<=tail) --tail;
q[++tail][0]=x;
q[tail][1]=f[t^1][x][y]+x;
f[t][x][y]=max(f[t][x][y],q[head][1]-x);
}
}
inline void work2(int y)
{
for(int x=0;x<=n;++x)
{
if(!a[x][y])
{
head=0,tail=-1;
continue;
}
while(x-q[head][0]>ed&&head<=tail) ++head;
while(f[t^1][x][y]-x>=q[tail][1]&&head<=tail) --tail;
q[++tail][0]=x;
q[tail][1]=f[t^1][x][y]-x;
f[t][x][y]=max(f[t][x][y],q[head][1]+x);
}
}
inline void work3(int x)
{
for(int y=m+1;y>=1;--y)
{
if(!a[x][y])
{
head=0,tail=-1;
continue;
}
while(q[head][0]-y>ed&&head<=tail) ++head;
while(f[t^1][x][y]+y>=q[tail][1]&&head<=tail) --tail;
q[++tail][0]=y;
q[tail][1]=f[t^1][x][y]+y;
f[t][x][y]=max(f[t][x][y],q[head][1]-y);
}
}
inline void work4(int x)
{
for(int y=0;y<=m;++y)
{
if(!a[x][y])
{
head=0,tail=-1;
continue;
}
while(y-q[head][0]>ed&&head<=tail) ++head;
while(f[t^1][x][y]-y>=q[tail][1]&&head<=tail) --tail;
q[++tail][0]=y;
q[tail][1]=f[t^1][x][y]-y;
f[t][x][y]=max(f[t][x][y],q[head][1]+y);
}
}
signed main()
{
n=read(),m=read(),x=read(),y=read(),k=read();
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
for(ch=getchar();(ch!='.'&&ch!='x');ch=getchar());
a[i][j]=(ch=='.');
}
}
memset(f,-0x3f,sizeof(f));
f[t][x][y]=0;
for(int p=1;p<=k;++p)
{
st=read(),ed=read(),d=read();
ed=ed-st+1;
t^=1;
if(d==1)//北
for(int j=1;j<=m;++j) work1(j);
if(d==2)//南
for(int j=1;j<=m;++j) work2(j);
if(d==3)//西
for(int i=1;i<=n;++i) work3(i);
if(d==4)
for(int i=1;i<=n;++i) work4(i);
}
for(int x=1;x<=n;++x)
for(int y=1;y<=m;++y)
ans=max(ans,f[t][x][y]);
printf("%d
",ans);
return 0;
}