EEOJ/OJ6
ClF3 b875e8e62a first commit 2024-07-04 00:37:16 +08:00
..
README.md first commit 2024-07-04 00:37:16 +08:00
main.cpp first commit 2024-07-04 00:37:16 +08:00

README.md

跳跳乐

by 陈宇豪

时间限制: 2000 ms 内存限制: 1500 KB

问题描述

有一系列相邻的台阶,每级台阶具有不同的高度,台阶间的水平距离相等,如图所示

有一只青蛙在不同台阶之间跳跃设青蛙可以跳跃的最长水平距离为K个台阶最大的垂直距离为H需要注意的是为简化问题垂直距离只需考虑跳跃起点和终点的高度差不需要考虑途中经过的台阶高度和起点的高度差以上图为例若K=5H=2则青蛙可以从当前位置跳跃到编号为{0, 3, 6}的三个台阶因为这三个台阶与当前台阶的水平距离均不大于5且垂直距离的绝对值分别为{2, 1, 1}均不大于2。

现在总共有M个连续台阶并给定每个台阶的高度试求青蛙一共可能在多少对台阶间跳跃

输入格式

输入为两行

第一行为三个整数分别为台阶数量M青蛙可以跳跃的最长水平距离K可以跳跃的最大垂直距离H

第二行为M个整数依次为各个台阶的高度

输出格式

输出为一个整数,为青蛙可以跳跃的台阶对数

输入样例

9 5 2

6 8 5 7 4 3 9 2 10

输出样例

14

// 可跳跃的台阶对编号分别为(0, 1), (0, 2), (0, 3), (0, 4), (1, 3), (1, 6), (2, 3), (2, 4), (2, 5), (3, 6), (4, 5), (4, 7), (5, 7), (6, 8)

提示

输入数据范围:

M<1×10^5K<5×10^4H<2^31每级台阶的高度也小于2^31

相邻两个台阶间的水平距离均相等且值为1任意两个台阶的高度均不相等