这道题的DP其实蛮简单的 (但我没想出来)
主要就是在单调队列优化这方面
那我就再提一次吧!
本题的单调队列优化
这里的队列并不是直接取伤害的值,而是存着地址
我们可以通过q(队列)中的元素来找到dp中的元素
那么我们认为q[h]存着最低伤害的方案
为了保证f[i]取q中元素是合法的,也就是说,q中的元素必须在i−R−1以内,不然跳不到i上面。
所以要加上这一句:
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;
}
Jackma_mayichao
发布了75 篇原创文章 · 获赞 13 · 访问量 2847
私信
关注