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

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

本题的单调队列优化

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

为了保证f[i]f[i]f[i]取qqq中元素是合法的,也就是说,qqq中的元素必须在iR1i-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;
}
2020.2.25普及C组 跳棋(jump) 【纪中】【DP】【单调队列优化】2020.2.25普及C组 跳棋(jump) 【纪中】【DP】【单调队列优化】 Jackma_mayichao 发布了75 篇原创文章 · 获赞 13 · 访问量 2847 私信 关注
上一篇:左手右手一个(不是)从左逆右逆广义逆到求解线性方程组的最小二乘解


下一篇:【Leetcode】236. Lowest Common Ancestor of a Binary Tree