题解 | #合唱队#

 反复对两侧递归

#include <stdio.h>
#define max(a,b)(a>b)?a:b;
int howmany[10010],rehowmany[10010],allhowmany[10010];
int n;
int arr[10010];
int maxnum;
void getscore(int *arr)
{
    maxnum=1;
    for(int i=0;i<n;i++)
    {
        howmany[i]=1;
        for(int j=0;j<i;j++)
        if(arr[i]>arr[j])
        howmany[i]=max(howmany[i],howmany[j]+1);
    }
    for(int i=n-1;i>=0;i--)
    {
        rehowmany[i]=1;
        for(int j=n-1;j>i;j--)
        if(arr[i]>arr[j])
        rehowmany[i]=max(rehowmany[i],rehowmany[j]+1);
        allhowmany[i]=howmany[i]+rehowmany[i]-1;
        maxnum=max(maxnum,allhowmany[i]);
    }
    return;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&arr[i]);
    getscore(arr);
    int a=n-maxnum;
    printf("%d",a);
    return 0;
}