2020.2.25普及C组 跳棋(jump) 【纪中】【DP】【单调队列优化】

这道题的DP其实蛮简单的 （但我没想出来）
主要就是在单调队列优化这方面
那我就再提一次吧！

本题的单调队列优化

这里的队列并不是直接取伤害的值，而是存着地址
我们可以通过qqq(队列)中的元素来找到dp中的元素
那么我们认为q[h]q[h]q[h]存着最低伤害的方案

为了保证f[i]f[i]f[i]取qqq中元素是合法的，也就是说，qqq中的元素必须在i−R−1i-R-1i−R−1以内，不然跳不到iii上面。

所以要加上这一句：
while(h<=t&&q[h]<i-R-1) h ;

---

会了本题的单调队列之后就能做了

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int n,l,r,f[1000010],a[1000010];int h,t,q[1000010];int main(){    freopen("jump.in","r",stdin);    freopen("jump.out","w",stdout);    cin>>n>>l>>r;    for(int i=1; i<=n; i  )     {     	cin>>a[i];     	f[i]=16843009;     }    h=1;    for(int i=1; i<=n; i  )     {     	if(i-l-1>=0)     	 {     	 	while(h<=t&&f[q[t]]>=f[i-l-1])     	 	 t--;     	 	t  ;     	 	q[t]=i-l-1;     	 }     	while(h<=t&&q[h]<i-r-1)     	  h  ;     	if(h<=t)     	  f[i]=a[i] f[q[h]];     }   if(f[n]<16843009)     cout<<f[n];   else     cout<<-1;   return 0;