洛谷 1091 合唱队形(NOIp2004提高组）

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 #define rg register
 6 #define N 200010
 7 using namespace std;
 8 int n,f[N],f2[N],a[N],t[N],ans;
 9 bool u[N];
10 inline int read(){
11     int k=0,f=1; char c=getchar();
12     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
13     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
14     return k*f;
15 }
16 inline int max(int x,int y){return x>y?x:y;}
17 inline void add(int x,int y){for(;x<=N;x+=(x&-x)) t[x]=max(t[x],y);}
18 inline int query(int x){int ret=0; for(;x;x-=(x&-x))ret=max(ret,t[x]); return ret;}
19 int main(){
20     n=read();
21     for(rg int i=1;i<=n;i++) a[i]=read();
22 //    for(rg int i=1;i<=n;i++) f[i]=f2[i]=1;
23     for(rg int i=1;i<=n;i++){
24         f[i]=query(a[i]-1)+1;
25         add(a[i],f[i]);
26     }
27     memset(t,0,sizeof(t));
28     for(rg int i=n;i;i--){
29         f2[i]=query(a[i]-1)+1;
30         add(a[i],f2[i]);
31     }
32     for(rg int i=0;i<=n;i++) ans=max(ans,f[i]+f2[i]-1);
33 //    for(rg int i=1;i<=n;i++) printf("%d ",f[i]); puts("");
34 //    for(rg int i=1;i<=n;i++) printf("%d ",f2[i]); puts("");
35     printf("%d\n",n-ans);
36     return 0;
37 }