这道题的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;
联系客服