单调队列
模版题
我们先考虑最小值。
我们发现如果有个比他小，出现的又比他早，那么它不可能成为答案。
也就是说可以 pop 了。
如果有一个人比你年龄小，又比你厉害，那么你就可以被pop了
如果有一个数跳出滑动窗口也 pop。
那么可以发现队列里的数是单调上升的。
第一个就是答案。
最大值也是同理。
这里给出最小值的代码。
for(int i=1;i<=n;++i)
{
while(h<=t&&a[i]<=a[q[t]]) t--;//弹出无用点
q[++t]=i;
while(h<=t&&i-q[h]>=k) h++;//弹出过时点
if(i>=k) printf("%d ",a[q[h]]);
}
单调队列优化dp
模版题
n^2 的 dp 大家都会吧，这里不讲了。
我们用一个单调队列，维护 dp 的值，队首就是最大的，然后转移。
没理解的看代码。
记得 dp 赋成 -10^{10} 。
答案怎么求自己想。
dp[0]=a[0];
for(int i=1;i<=n;++i)
if(i>=L)
{
while(!q.empty()&&dp[i-L]>=dp[q.back()]) q.pop_back();
q.push_back(i-L);
while(!q.empty()&&q.front()<i-R) q.pop_front();
dp[i]=dp[q.front()]+a[i];
}
下期讲啥，发帖我随机挑。