ZOJ 3349 Special Subsequence

Special Subsequence

Time Limit: 5000ms

Memory Limit: 32768KB

This problem will be judged on ZJU. Original ID: 3349
64-bit integer IO format: %lld Java class name: Main

There a sequence S with n integers , and A is a special subsequence that satisfies |Ai-Ai-1| <= d ( 0 <i<=|A|))

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 .Each integer 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

Sample Output

3
1

Source

ZOJ Monthly, June 2010

Author

CHEN, Zhangyi

解题：动态规划+线段树优化

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100100;
 4 int tree[maxn<<2],Lisan[maxn],a[maxn],tot,n,d;
 5 int query(int L,int R,int lt,int rt,int v){
 6     if(lt <= L && rt >= R) return tree[v];
 7     int mid = (L + R)>>1,ret = 0;
 8     if(lt <= mid) ret = query(L,mid,lt,rt,v<<1);
 9     if(rt > mid) ret = max(ret,query(mid + 1,R,lt,rt,v<<1|1));
10     return ret;
11 }
12 void update(int L,int R,int pos,int val,int v){
13     if(L == R){
14         tree[v] = max(tree[v],val);
15         return;
16     }
17     int mid = (L + R)>>1;
18     if(pos <= mid) update(L,mid,pos,val,v<<1);
19     if(pos > mid) update(mid + 1,R,pos,val,v<<1|1);
20     tree[v] = max(tree[v<<1],tree[v<<1|1]);
21 }
22 int main(){
23     while(~scanf("%d%d",&n,&d)){
24         memset(tree,0,sizeof tree);
25         for(int i = 0; i < n; ++i){
26             scanf("%d",a + i);
27             Lisan[i] = a[i];
28         }
29         sort(Lisan,Lisan + n);
30         tot = unique(Lisan,Lisan + n) - Lisan;
31         int ret = 0;
32         for(int i = 0; i < n; ++i){
33             int L = max(0,(int)(lower_bound(Lisan,Lisan + tot,a[i] - d) - Lisan + 1));
34             int R = min(tot,(int)(upper_bound(Lisan,Lisan + tot,a[i] + d) - Lisan));
35             int tmp = 1,pos = lower_bound(Lisan,Lisan + tot,a[i]) - Lisan + 1;
36             if(L <= R) tmp = query(0,tot,L,R,1) + 1;
37             ret = max(ret,tmp);
38             update(0,tot,pos,tmp,1);
39         }
40         printf("%d
",ret);
41     }
42     return 0;
43 }

View Code