本文是笔者第二篇解题报告。从现在开始，会将练的一些题发到博客上并归类到"解题报告"标签中。
琪露诺是这样一道题
这道题可以用纯DP做，但是据说会超时。(为什么？看起来过河这题比它数据大多了)于是到Luogu题解上找到了单调队列优化。
首先讲一下纯DP思路
假设我们的⑨正在河中央，编号为i的格子上。
观察琪露诺的移动规律可得，琪露诺再往下走只能走到编号为i + l 到 i + r 之间的格子上。
于是想到，琪露诺之所以现在能在这里，一定是上一步从编号为 i - r 到 i - l 的格子上其中一个，然后走过来。
所以用 i 横扫输入数组，用 j 爆搜 i - r 到 i - l 之间的所有格子，然后取一个冰冻指数最大的。
but这样会TLE
用单调队列。维护一个单调递减的队列，弹出队尾不符合性质的元素，弹出队首需要出队的元素，然后让当前元素进队，最后寻找答案。
代码在这里
#include<cstdio> #include<cctype> const int size=1000000; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*f; } int que[size],f[size],q[size]; int h=1,t; int ans; int main(){ int n=read(),l=read(),r=read(); for(int i=0;i<=n;++i) que[i]=read(); for(int i=l;i<=n;++i){ while(q[f[t]]<=q[i-l]&&t>=h) t--; f[++t]=i-l; while(f[h]<i-r) h++; q[i]=q[f[h]]+que[i]; } ans=q[n-r+1]; for(int i=n-r+2;i<=n;++i) ans=ans>q[i]?ans:q[i]; printf("%d",ans); return 0; }