这是一道思路比较简单但是调试极其毒瘤的一道题目！
题目描述
一个猴子找到了很多香蕉树，这些香蕉树都种在同一直线上，而猴子则在这排香蕉树的第一棵树上。这个猴子当然想吃尽量多的香蕉，但它又不想在地上走，而只想从一棵树跳到另一棵树上。同时猴子的体力也有限，它不能一次跳得太远或跳的次数太多。每当他跳到一棵树上，它就会把那棵树上的香蕉都吃了。那么它最多能吃多少个香蕉呢？
输入格式
输入第一行为三个整数，分别是香蕉树的棵数NN，猴子每次跳跃的最大距离DD，最多跳跃次数MM。 下面NN行每行包含两个整数ai，biai，bi，分别表示每棵香蕉树上的香蕉数，以及这棵树到猴子所在树的距离。输入保证这些树按照从近到远排列，并且没有两棵树在同一位置。b0b0总是为0。
输出格式
输出只有一行，包含一个整数，为猴子最多能吃到的香蕉数。
样例一
input
5 5 2
6 0
8 3
4 5
6 7
9 10
output
20
限制与约定
对于30%的数据,1≤M<N≤1001≤M<N≤100
对于50%的数据,1≤M<N≤20001≤M<N≤2000
对于100%的数据,1≤M<N≤5000,ai≤10000,bi≤10000，D≤100001≤M<N≤5000,ai≤10000,bi≤10000，D≤10000
时间限制：1s1s
空间限制：256MB
首先是状态转移方程dp[k][i]表示到第i棵数已经跳了k步的最多香蕉数
那么转移就是dp[k][i]=max(dp[k-1][q[head]]+val[i],dp[k][i]);
然后呢就是毒瘤的单调队列时间
就是这种数据结构，把它弄成单调的，head弹出，tail插入；
在数组里是把整个队列倒过来放进去的
因为是单调队列
所以插入时候tail--找到要插的位置，然后再++tail位置插进去
弹出时候head++，就弹出了
也就是说在数组里head在左，tail在右，可以脑补这个队列就躺在数组里
一定要注意head要<=tail，要不可能会死循环（网上有个代码就被我hack了）
这道题有一些注意的地方；
有几组数据比较毒瘤，有可能有两个树之间距离很大，导致后面的树全都去不了（见16行特判，被卡掉了30分），这时候需要特殊处理（我直接输出，会跑的很快2333）
上代码！
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 int n,d,m,head=1,tail=1,ans=-1; 7 int val[5111],s[5111],dp[5111][5111],q[5111]; 8 int main() 9 { 10 scanf("%d%d%d",&n,&d,&m); 11 for(int i=1;i<=n;i++)scanf("%d%d",&val[i],&s[i]); 12 dp[0][1]=val[1]; 13 for(int k=1;k<=m;k++) 14 { 15 head=tail=1; 16 if(s[k+1]-s[k]>d) 17 { 18 for(int i=1;i<=k;i++) 19 ans=max(ans,dp[k-1][i]); 20 printf("%d ",ans); 21 return 0; 22 } 23 q[tail]=k; 24 for(int i=k+1;i<=n;i++) 25 { 26 while(head<=tail && s[i]-s[q[head]]>d) 27 head++; 28 dp[k][i]=max(dp[k-1][q[head]]+val[i],dp[k][i]); 29 while(head<=tail && dp[k-1][q[tail]]<dp[k-1][i]) 30 tail--; 31 q[++tail]=i; 32 } 33 } 34 for(int i=1;i<=n;i++)ans=max(ans,dp[m][i]); 35 printf("%d ",ans); 36 return 0; 37 }