题解 | #合唱队#

// HJ24 合唱队.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		//cin >> n;
		vector<int>num(n, 0);
		for (int i = 0; i < n; i++)
			cin >> num[i];
		vector<int>dp1(n, 0);
		vector<int>dp2(n, 0);
		for (int i = 0; i < n; i++)
		{
			dp1[i] = 1;
			for (int j = 0; j < i; j++)
			{
				if (num[i] > num[j])
				{
					dp1[i] = max(dp1[i], dp1[j] + 1);
				}
			}
		}
		for (int i = n - 1; i >= 0; i--)
		{
			dp2[i] = 1;
			for (int j = n - 1; j > i; j--)
			{
				if (num[i] > num[j])
				{
					dp2[i] = max(dp2[i], dp2[j] + 1);
				}
			}
		}
		int maxlen = 0;
		for (int i = 0; i < n; i++)
		{
			maxlen = max(maxlen, dp1[i] + dp2[i] - 1);
		}
		cout << n - maxlen << endl;
	}
	return 0;
}