题解 | #合唱队形#

#include <iostream>
#include <cstring>


using namespace std;

const int N = 110;

int a[N];
int dp[N];//以i为结尾的最长递增子序列
int dp2[N];//以i为开头的最长递减子序列

int main() {


    int n;
    while (cin >> n) {
        int ans = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        //求最长递增
        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j > 0; j--) {
                if (a[j] < a[i]) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
        }
        //求最长递减
        for(int i=n;i>0;i--){
            dp2[i]=1;
            for(int j=i+1;j<=n;j++){
                if(a[j] < a[i]){
                    dp2[i] = max(dp2[j]+1,dp2[i]);
                }
            }
        }
        for(int i=1;i<=n;i++){
            ans=max(ans,dp[i]+dp2[i]-1);
        }
        cout << n-ans << endl;

    }



    return 0;
}