#P18341. Wavelike Finding
Wavelike Finding
Wavelike Finding
标准输入,标准输出。
本题给定两个固定参数 和 。
对于一个长度恰好为 的序列 ,如果
就称这个序列是 shaky 的。
对于一个序列 ,如果它同时满足以下两条,就称它是 wavelike 的:
- ;
- 它至少含有一个 shaky 子序列。这里的子序列不要求连续,但必须保持原来的相对顺序。
现在给定序列 。请从中选择尽可能多段互不重叠的 wavelike 连续子序列。
被选的每一段必须是原序列中的一个连续区间;不同区间不能共用位置。这些区间不需要覆盖整个序列,可以在相邻两段之间留下未选的位置。
输入格式
第一行包含三个整数 。
第二行包含 个整数 。
输出格式
输出一行一个整数,表示最多能够选出多少段互不重叠的 wavelike 连续子序列。
数据范围
- ;
- ;
- ;
- 。
输入只有一组数据。
样例输入 1
9 2 25
6 4 3 5 7 1 2 5 8
样例输出 1
2
样例输入 2
9 2 30
6 4 3 5 7 1 2 5 8
样例输出 2
1
样例输入 3
2 1 1
0 0
样例输出 3
0
样例输入 4
2 1 -6
-1 -5
样例输出 4
1
样例说明
第三组样例中,唯一的两项子序列得分为0,小于1,因此答案为0。第四组样例中,两个数之和恰好为-6,满足大于等于门槛的要求,因此答案为1。