HDU 5256 - 序列变换 ，树状数组+离散化 ，二分法

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 int c[1000000],n,t,len,a;
 5 int find(int l,int r,int num){
 6     while(l<=r){ int mid=(l+r)>>1; if(c[mid]<=num) l=mid+1; else r=mid-1; }
 7     return l;
 8 }
 9 int main(){
10     scanf("%d",&t);
11     for(int k=1;k<=t;k++){
12         printf("Case #%d:\n",k);
13         scanf("%d",&n);
14         len=1; memset(c,0,sizeof(c));
15         for(int i=1;i<=n;i++){
16             scanf("%d",&a);
17             if(i==1){ c[len]=a-i; continue;    }
18             int pos=find(1,len,a-i);
19             c[pos]=a-i;
20             if(len<pos) len=pos;
21         }    printf("%d\n",n-len);
22     } return 0;
23 }

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 #define N 1000000+5
 6 int c[N],a[N],b[N],n,t,nmax;
 7 void modify(int x,int num){while(x<=nmax)c[x]=max(c[x],num),x+=x&-x;}
 8 int query(int x){int s=0;while(x>0)s=max(c[x],s),x-=x&-x;return s;}
 9 int main(){
10     scanf("%d",&t);
11     for(int k=1;k<=t;k++){
12         printf("Case #%d:\n",k);
13         scanf("%d",&n);
14         memset(c,0,sizeof(c)); nmax=0;
15         for(int i=0;i<n;i++){
16             scanf("%d",&a[i]);
17             a[i]-=i; b[i]=a[i]; 
18         } 
19         sort(b,b+n); 
20         int size=unique(b,b+n)-b;//离散化 
21         for(int i=0;i<n;i++){
22             a[i]=lower_bound(b,b+size,a[i])-b+1;
23             nmax=max(a[i],nmax);//离散化以后再去标记最大值 
24         } 
25         for(int i=0;i<n;i++)modify(a[i],query(a[i])+1);//前缀最大值+1 
26         printf("%d\n",n-query(nmax));
27     } return 0;
28 }