TSL序列

发布时间: 2018年1月29日 10:26   最后更新: 2018年2月11日 23:54   时间限制: 5000ms   内存限制: 256M

TSL序列的定义是满足$|a_i-a_{i-1} |≤d$,$(0<i≤|a|)$的序列。现在给你一个有$n$个元素的序列,求出这个序列的最长TSL子序列的长度。

有多组测试数据,(数据组数$≤20$)。对于每组数据,第一行有两个整数$n,d$如题目所述。第二行有$n$个数$a_1,a_2,…,a_n$,中间以空格分割。
$1≤n≤10^5$
$0≤d≤10^8$
$0≤a_i≤10^8$

对于每组测试数据,输出一个整数表示该序列的最长TSL子序列的长度。

复制
5 2
1 4 3 6 5
5 0
1 2 3 4 5
3
1

本题的输入数据量较大,建议使用高效的读写方式:C++使用scanf/printf代替cin/cout,Java使用BufferedReader/PrintWriter代替Scanner/System.out。

第一个样例:最长TSL子序列为1,3,5,长度为3

dp data structure

Weekly Training 2018.1.28