rnqoj-28-合唱队形-最长上升子序列

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
int main()  
{  
    int i,n,j,a[201];  
    cin>>n;  
    for(i=1;i<=n;i++)  
    {  
        scanf("%d",&a[i]);  
    }  
    int dp1[201];  
    int dp2[201];  
    memset(dp1,0,sizeof(dp1));  
    memset(dp2,0,sizeof(dp2));  
    for(i=1;i<=n;i++)  
    {  
        int ma=1;  
        for(j=1;j<i;j++)  
        {  
            if(a[j]<a[i])ma=max(ma,dp1[j]+1);  
        }  
        dp1[i]=ma;  
    }  
    for(i=n;i>=1;i--)  
    {  
        int mb=1;  
        for(j=n;j>i;j--)  
        {  
            if(a[j]<a[i])mb=max(mb,dp2[j]+1);  
        }  
        dp2[j]=mb;  
    }  
    int ans=0;  
    for(i=1;i<=n;i++)  
    {  
        ans=max(dp2[i]+dp1[i]-1,ans);  
    }  
    cout<<n-ans<<endl;  
    return 0;  
}