题解 | #合唱队形#

#include <stdio.h>

void fun_up(int *stu,int i,int n,int *up)
{

        int max=1;
        for(int j=0;j<i;j++)
        {
            if(up[j]+1>max&&stu[j]<stu[i])max=up[j]+1;
        }
        up[i]=max;
}

void fun_down(int *stu,int i,int n,int *down)
{

        int max=1;
        for(int j=n-1;j>i;j--)
        //注意down的时候一定要从n到i反向计算
        {
            if(down[j]+1>max&&stu[j]<stu[i])max=down[j]+1;
        }
        down[i]=max;
}




int main() {
   int n;
   scanf("%d",&n);
   int stu[100];
   int up[100]={0};
   int down[100]={0};
   up[0]=1;
   down[n-1]=1;
   for(int i=0;i<n;i++)scanf("%d",&stu[i]);
   int sum=n;
   for (int i=0;i<n;i++)fun_up(stu, i, n, up);
   for (int i=n-1;i>=0;i--)fun_down(stu, i, n, down);
   //注意down的时候一定要从n到i反向计算
   for(int i=0;i<n;i++)
   {    

        int f1=up[i];
        //printf("%d\n",f1);
        int f2=down[i];
        //printf("%d %d %d\n",f1,f2,n-f1-f2+1);
        if(n-f1-f2+1<sum)sum=n-f1-f2+1;
   }
    printf("%d",sum);
    return 0;
}
// #include <stdio.h>
// int main()
// {
// printf("4");
// }