题解 | #合唱队形#

#include <bits/stdc++.h>
using namespace std;
vector<int>h;
int n;
int long_up(int l,int r)
{
    int maxl=1;
    int dp[100];
    for(int i=0;i<100;i++) dp[i]=1;
    for(int i=l;i<=r;i++)
    {
        for(int j=l;j<i;j++)
        {
            if(h[i]>h[j]) 
            {
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        maxl=max(maxl,dp[i]);
    }
    return maxl;
}
int main() {
    while(cin>>n)
    {
        h.clear();
        int data;
        for(int i=0;i<n;i++)
        {
            cin>>data;
            h.push_back(data);
        }
        //从前往后，计算以i收尾的最长上升子序列
        int a[n];
        for(int i=0;i<h.size();i++)
        {
            a[i]=long_up(0,i);
        }
        //从后往前，计算以n-1-i收尾的最长上升子序列
        int b[n];
        reverse(h.begin(),h.end());
        for(int i=0;i<h.size();i++)
        {
            b[i]=long_up(0,i);
        }
        int maxl=1;
        //统计0~n-1，取能够组成合唱队的最大值，即a[i]+b[n-1-i]-1的最值
        for(int i=0;i<n;i++)
        { 
            maxl=max(maxl,a[i]+b[n-1-i]-1);
        }
        cout<<n-maxl;
    }
}
// 64 位输出请用 printf("%lld")