ZOJ3349——Special Subsequence
Special Subsequence
Time Limit: 5 Seconds
Memory Limit: 32768 KB
There a sequence S with n integers , and A is a special subsequence thatsatisfies |Ai-Ai-1| <=
d ( 0
Now your task is to find the longest special subsequence of a certain sequence
S
Input
There are no more than 15 cases , process till the end-of-file
The first line of each case contains two integer n and d ( 1<=n<=100000 ,0<=d<=100000000) as in the description.
The second line contains exact n integers , which consist the sequnece
S .Eachinteger is in the range [0,100000000] .There is blank between each integer.
There is a blank line between two cases
Output
For each case , print the maximum length of special subsequence you can get.
Sample Input
5 2
1 4 3 6 5
5 0
1 2 3 4 5
Sample Output
3
1
水dp+水線段樹
哈哈今天的第一個1Y
#include