单调队列

就是一个队列，单调递减或者但单调递增，就是这样，没了... 再举个例子： 3 0  2 7 2 5  这是我初高中的几个学号，用一个c[max]存为单调递增队列，再用d数组存储每个c队列中元素在原数列中的位置id l存储起始位置，r存储队尾， 开始 3 然后 0<3 r--  ——>0 0,2 next 0，2，7 最后 2<7 取缔7 2<=2 取缔2（对d数组有影响） ....... 然后真没了 例题：

题目背景

据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。

然而当时灵梦在Power达到MAX之前，不具有“上线收点”的能力，所以她想要知道她能收集多少P点，然而这个问题她答不上来，于是她找到了学OI的你。

题目描述

可以把游戏界面理解成一个N行M列的棋盘，有K个格子上有P点，其价值为val(i,j)

初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。

灵梦具有一个左右移动的速度T，可以使她每秒向左或右移动至多T格,也可以不移动，并且不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的P点。

求最终她能获得的POWER值最大是多少？

输入输出格式

输入格式：

第一行四个数字，N,M,K,T

接下来K行每行3个数字x,y,v,代表第x行第y列有一个val为v的P点，数据保证一个格子上最多只有1个P点。

输出格式：

一个数字

输入输出样例

输入样例#1： 3 3 4 1 1 1 3 1 2 1 2 2 3 3 3 3 输出样例#1： 9

说明

对于40%的测试点，1<=N,M,T,K<=200

对于100%的测试点，1<=N,M,T,K<=4000

v<=100，N,M,K,T均为整数

代码

made by 罗旅洲

#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int map[4010][4010],c[4010],dp[4010][4010],d[4010],l,r; void insert(int x,int id){ c[++r]=x; while(r>l && c[r]>=c[r-1]) c[--r]=c[r+1]; d[r]=id; } int main(){ #ifndef ONLINE_JUDGE freopen("input.in","r",stdin); freopen("output.out","w",stdout); #endif int i,j,k,n,m,q,v,a,b; scanf("%d%d%d%d",&n,&m,&q,&v); while(q--){ scanf("%d%d%d",&a,&b,&k); map[a][b]=k; } for(i=1;i<=m;i++)dp[1][i]=map[1][i]; for(i=2;i<=n;i++){ c[1] = dp[i-1][1]; d[1]=l=r=1; for(j=2;j<=min(m,1+v);j++) insert(dp[i-1][j],j); for(j=1;j<=m;j++){ if(j+v<=m)insert(dp[i-1][j+v],j+v); if(j-v>1 && j-v-1 == d[l])l++; dp[i][j]= c[l]+ map[i][j]; } } int ans=0; for(i=1;i<=m;i++) ans=max(ans,dp[n][i]); printf("%d",ans); return 0; }