题解 | 合唱队形

//KY72 合唱队形
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[105], dp1[105], dp2[105];
int main()
{
    while(cin>>n)
    {
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            dp1[i]=1;
            for(int j=1;j<i;j++){
                if(a[i]>a[j]) dp1[i]=max(dp1[j]+1,dp1[i]);
            }
        }
        for(int i=n;i>0;i--){
            dp2[i]=1;
            for(int j=n;j>i;j--){
                if(a[j]<a[i]) dp2[i]=max(dp2[j]+1,dp2[i]);
            }
            //cout<<dp2[i]<<' ';
        }
        int num=1;
        for(int i=1;i<=n;i++){
            num=max(dp1[i]+dp2[i],num);
        }
        cout<<n-num+1<<'\n';
    }
    return 0;
}