题解 | #合唱队形#

正反两个方向各求一次最长递增子序列，分别记录在dp_qianxiang和dp_houxiang两个数组，最后将两个相加得到sum[i]表示以i为最高点的最长的队形，需要注意的是最高点会被算两次，因此相加的时候要-1

写于2024.3.17，祝考研复试顺利

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int a[maxn];            // a数组记录每个人的高度
int dp_qianxiang[maxn]; // dp_qianxiang[i]组代表以i为结尾的最长递增子序列
int dp_houxiang[maxn];  // dp_houxiang[i]组代表以i为结尾的最长递增子序列，从后向前看
int sum[maxn];

int main()
{
    int n, i, j, answer = 0;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (i = 0; i < n; i++)
    {
        dp_qianxiang[i] = 1;
        for (j = 0; j < i; j++)
        {
            if (a[i] > a[j])
                dp_qianxiang[i] = max(dp_qianxiang[i], dp_qianxiang[j] + 1);
        }
        // cout << dp_qianxiang[i];
    }
    // cout << endl;
    reverse(a, a + n); // 反转函数
    for (i = 0; i < n; i++)
    {
        dp_houxiang[i] = 1;
        for (j = 0; j < i; j++)
        {
            if (a[i] > a[j])
                dp_houxiang[i] = max(dp_houxiang[i], dp_houxiang[j] + 1);
        }
        // cout << dp_houxiang[i];
    }
    reverse(dp_houxiang, dp_houxiang + n);
    // cout << endl;
    for (i = 0; i < n; i++)
    {
        sum[i] = dp_qianxiang[i] + dp_houxiang[i] - 1;
        answer = max(sum[i], answer);
    }
    cout << n - answer;

    return 0;
}