p3670.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
using namespace std;
const int MAXN=30000;
int a[MAXN+1],f[4],t[4];
int i,j,n,ma;
int main(){
    memset(t,0,sizeof(t));
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=n;i>0;i--){
        f[a[i]]=1;
        for(j=1;j<=a[i];j++)
            if(t[j]+1>f[a[i]]) f[a[i]]=t[j]+1;
        t[a[i]]=f[a[i]];
    }
    ma=f[1];
    if(f[2]>ma) ma=f[2];
    if(f[3]>ma) ma=f[3];
    for(i=1;i<=3;i++){
        f[i]=0;
        t[i]=0;
    }
    for(i=1;i<=n;i++){
        f[a[i]]=1;
        for(j=1;j<=a[i];j++)
            if(t[j]+1>f[a[i]]) f[a[i]]=t[j]+1;    
        t[a[i]]=f[a[i]];
    }
    for(i=1;i<=3;i++)
        if(f[i]>ma) ma=f[i];
    cout<<n-ma<<endl;
}