（纪中）2170. 跳棋【单调队列】

(File IO): input:jump.in output:jump.out
时间限制: 1000 ms 空间限制: 131072 KB 具体限制

题目描述
小明迷恋上了一个新的跳棋游戏，游戏规则如下：棋盘是一排从$0$开始，顺序编号的格子，游戏开始时你位于$0$号格子，你每次只能往编号大的格子跳，而且你每次至少需要跳过$L$个格子，至多只能跳过$R$个格子。每个格子都有一个给定的伤害值，显然你希望得到的伤害值越少越好。
你能告诉小明他当他跳到最后一个格子时受到的累积伤害值最小为多少吗？
如果无论如何小明都无法跳到最后一个格子，这个时候你需要输出$”-1”$。
注：从i号格子跳过$x$个格子表示从i号格子跳到第$i+x+1$号格子。

输入
输入文件$jump.in$第一行有三个整数$n、L$和$R，n$表示格子的编号从$0$到$n$。$L$和$R$表示最少需要跳过的格子数和最多能够跳过的格子数。
第二行有$n$个正整数，两个数字间用空格隔开，表示每个格子的伤害值。

输出
输出文件$jump.out$仅有一个整数，表示受到的最小伤害值，保证结果小于$maxlongint$。

样例输入
10 2 6
1 3 5 7 9 2 4 6 8 10

样例输出
12

数据范围限制
$50$%的数据，$1<=n<=1000$
$65$%的数据，$1<=n<=10000$
$100$%的数据，$1<=n<=1000000，1<=L<=R<=n$
其中有$15$%的数据，$1<=n<=1000000，1<=L<=R<=10$

提示

解题思路
这道题显而易见的是动态规划。转移方程也非常好推，我们把 $f[i]$ 作为到第I格的最小伤害值，转移方程就是
$f[i]=minf[j](j=i-r-1i-l-1)+a[i]；$
显而易见，动态规划的时间复杂度是$O（n\ast n）$的，肯定TLE，但是有没有一种算法可以快速枚举区间最值呢？
有四种方法：$（1）$优先队列$（2）$线段树 （3）堆$（4）$单调队列
而我们这次讲解最简易的单调队列解法，
单调队列最本质的本质就是用来求定区间最值的，用它也非常方便。

代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
int n,l,r,h,t;
long long f[1000010],q[1000010],a[1000010];
int main()
{freopen("jump.in","r",stdin);freopen("jump.out","w",stdout);scanf("%d%d%d",&n,&l,&r);for(int i=1; i<=n; i++){scanf("%lld",&a[i]);f[i]=2147483647;}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]<2147483647)printf("%lld",f[n]);elsecout<<-1;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！