ZOJ 3349 Special Subsequence

题意就不多说了，其实就是一个dp优化题目。
  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 #define lson l,m,rt<<1
  5 #define rson m+1,r,rt<<1|1
  6 #define maxn 100005
  7 struct node{
  8     int sum;
  9 }setree[maxn<<2];
 10 int sorted[maxn],num[maxn];
 11 void build(int l,int r,int rt)
 12 {
 13     setree[rt].sum=0;
 14     if(l==r)
 15     return;
 16     int m=(l+r)>>1;
 17     build(lson);
 18     build(rson);
 19 }
 20 int binsearch1(int l,int r,int num,int &pos)
 21 {
 22     if(l>r)
 23     return pos;
 24     int m=(l+r)>>1;
 25     if(sorted[m]>=num){
 26         pos=m;
 27         return binsearch1(l,m-1,num,pos);
 28     }
 29     return binsearch1(m+1,r,num,pos);
 30 }
 31 int binsearch2(int l,int r,int num,int &pos)
 32 {
 33     if(l>r)
 34     return pos;
 35     int m=(l+r)>>1;
 36     if(sorted[m]<=num){
 37         pos=m;
 38         return binsearch2(m+1,r,num,pos);
 39     }
 40     return binsearch2(l,m-1,num,pos);
 41 }
 42 int binsearch(int l,int r,int num)
 43 {
 44     int m=(l+r)>>1;
 45     if(sorted[m]==num)
 46     return m;
 47     if(num<sorted[m])
 48     return binsearch(l,m-1,num);
 49     return binsearch(m+1,r,num);
 50 }
 51 void pushup(int rt)
 52 {
 53     setree[rt].sum=max(setree[rt<<1].sum,setree[rt<<1|1].sum);
 54 }
 55 void update(int l,int r,int rt,int pos,int num)
 56 {
 57     if(l==r){
 58         setree[rt].sum=num;
 59         return;
 60     }
 61     int m=(l+r)>>1;
 62     if(pos<=m)
 63     update(lson,pos,num);
 64     else
 65     update(rson,pos,num);
 66     pushup(rt);
 67 }
 68 int query(int l,int r,int rt,int L,int R)
 69 {
 70     if(L<=l&&r<=R)
 71     return setree[rt].sum;
 72     int m=(l+r)>>1,ans=0;
 73     if(L<=m)
 74     ans=max(ans,query(lson,L,R));
 75     if(R>m)
 76     ans=max(ans,query(rson,L,R));
 77     return ans;
 78 }
 79 int main()
 80 {
 81     int n,d;
 82     while(~scanf("%d%d",&n,&d)){
 83         for(int i=1;i<=n;i++){
 84             scanf("%d",&num[i]);
 85             sorted[i]=num[i];
 86         }
 87         sort(sorted+1,sorted+n+1);
 88         int k=1;
 89         for(int i=2;i<=n;i++)
 90         if(sorted[i]!=sorted[i-1])
 91         sorted[++k]=sorted[i];
 92         build(1,k,1);
 93         int ans=0,pos1,pos2;
 94         for(int i=1;i<=n;i++){
 95             int pos=binsearch(1,k,num[i]);
 96             int l=binsearch1(1,k,num[i]-d,pos1);
 97             int r=binsearch2(1,k,num[i]+d,pos2);
 98             //printf("pos=%d l=%d r=%d
",pos,l,r);
 99             int tmp=query(1,k,1,l,r);
100             ans=max(ans,tmp+1);
101             update(1,k,1,pos,tmp+1);
102         }
103         printf("%d
",ans);
104     }
105     return 0;
106 }
AC Code