小明迷恋上了一个新的跳棋游戏游戏规则如下：跳棋棋盘java是一排从0开始，顺序编号的格子游戏开始时你位于0号格子，你每次只能往编号大的格子跳而且你每次至少需要跳过L个格子，至多只能跳过R个格子每个格子都有一个给定的伤害值，显然你希望得到的伤害值越少越好
你能告诉小明他当他跳到朂后一个格子时受到的累积伤害值最小为多少吗？
如果无论如何小明都无法跳到最后一个格子这个时候你需要输出”-1”。
注：从i号格子跳过x个格子表示从i号格子跳到第i+x+1号格子
输入文件jump.in第一行有三个整数n、L和R，n表示格子的编号从0到nL和R表示最少需要跳过的格子数和最多能夠跳过的格子数。
第二行有n个正整数两个数字间用空格隔开，表示每个格子的伤害值
输出文件jump.out仅有一个整数，表示受到的最小伤害值保证结果小于maxlongint。
这道题很明显是动态规划
现在问题出现了，如何优化时间
方程中的f[i-r-1~i-l-1]原本需要枚举，我们能不能用O(1)的时间找出其中的朂小值有三种方法：堆维护，单调队列或线段树下面附上堆维护的标程。
发布了27 篇原创文章 · 获赞 4 · 访问量 1万+
