背景
题目来源:【HT-126-Div.2】核桃 CSP-S 组模拟赛
题目描述
给定一个长度为 n 的正整数序列 A={A1,A2,…,An},以及非负整数 k 和正整数 d。
你可以构造一个正整数多重集合 B,要求满足 ∣B∣≤k(即集合 B 中最多包含 k 个元素,且元素可以任意指定)。
令集合 S=A∪B。你需要从 S 中选出一个子集 T⊆S,使得 T 中的元素在按严格递增顺序排列后 t1<t2<⋯<tm,能够满足:
- 对于任意 1≤i<m,均有 ti+1−ti≤d。
求 ∣T∣ 的最大值(即 m 的最大值)。
输入格式
输入共两行。
第一行,三个整数 n,k,d。
第二行,包含 n 个正整数表示序列 Ai。
输出格式
输出共一行,一个整数表示 ∣T∣ 的最大值。
5 1 2
1 4 8 9 13
4
8 2 3
10 15 2 4 16 11 5 20
9
提示
【样例解释 #1】
对于样例 #1,原序列 A 去重并排序后为 {1,4,8,9,13}。
我们可以选择 A 中的子集 {4,8,9},并构造集合 B={6}(只使用了 1 个元素,满足 ∣B∣≤1)。
此时 T={4,6,8,9},排序后相邻两项的差值分别为 2,2,1,均不超过 d=2。集合 T 的大小为 4。
【样例解释 #2】
对于样例 #2,原序列 A 去重排序后为 {2,4,5,10,11,15,16,20}。
选取 A 中的 {2,4,5,10,11,15,16},并令 B={8,14}。
此时 T={2,4,5,8,10,11,14,15,16},相邻差值最大为 3,大小为 9。
【数据范围】
本题采用捆绑测试。
对于所有测试数据,保证: 1≤n≤105,0≤k≤109,1≤d,Ai≤109。
| 子任务编号 |
n≤ |
特殊性质 |
分值 |
| 1 |
102 |
k=0 |
15 |
| 2 |
103 |
无 |
| 3 |
105 |
k=0 |
20 |
| 4 |
d=1 |
| 5 |
无 |
30 |