题解 | #合唱队#

#include <stdio.h>//最长递增子序列
#include <string.h>
#include <stdlib.h>
void stu_out(int stu[3000],int n)
{
    int i,j,top=0,topp;
    int left[3000],right[3000];
    left[0]=1;
    for(i=1;i<n;i++)
    {
        top=0;
        for(j=0;j<i;j++)
        if((top<left[j])&&(stu[i]>stu[j])) top=left[j];
        left[i]=top+1;
    }
    right[n-1]=1;
    for(i=1;i<n;i++)
    {
        top=0;
        for(j=0;j<i;j++)
        if((top<right[n-1-j])&&(stu[n-1-i]>stu[n-1-j])) top=right[n-1-j];
        right[n-1-i]=top+1;
    }
    for(i=0;i<n;i++)
    {
        left[i]+=right[i];
    }
    top=0;
    for(i=0;i<n;i++)
    {
        if(left[i]>top) 
        {
            top=left[i];
            topp=i;
        }
    }
    printf("%d\n",n-left[topp]+1);
}

int main(void) 
{ 
    int n,i,stu[3000];
    while(scanf("%d",&n)!=-1)
    {
        for(i=0;i<n;i++)
        {
	        scanf("%d",stu+i);
	    }
	    stu_out(stu,n);
    }
	return 0;
}