题解 | #合唱队形#

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> dp1(n); //最长递增子序列
		vector<int> dp2(n); //最长不递增子序列
		vector<int> arr(n);
		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
			dp1[i] = 1;
			dp2[i] = 1;
		}

		for (int i = 0; i < n; i++)
		{
			//以i为结尾的最长递增子序列
			for (int j = 0; j < i; j++)
			{
				if (arr[i] > arr[j])
				{
					dp1[i] = max(dp1[i], dp1[j] + 1);
				}
			}
		}

		//还要求以i为开头的最长递减子序列
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = n - 1; j > i; j--)
			{
				if (arr[i] > arr[j])
				{
					dp2[i] = max(dp2[i], dp2[j] + 1);
				}
			}
		}

		for (int i = 0; i < n; i++)
		{
            if(i==0||i==n-1)
            {
                dp1[i] = dp1[i] + dp2[i] - 1;
                continue;
            }
			//只有当前后均有元素时才能按照此法
            if(dp1[i]>1&&dp2[i]>1)
            {
                dp1[i] = dp1[i] + dp2[i]-1;
            }else
            {
                dp1[i] = 1;
            }
		}
		int ans =  n - *max_element(dp1.begin(), dp1.end());
		cout << ans;
	}
	return 0;
}