题解 | #合唱队#

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> res;
    for (int i  = 0; i < N; i++) {
        int n;
        cin >> n;
        res.push_back(n);
    }

    // for (vector<int>::iterator it = res.begin(); it != res.end(); ) { //去重
    //     if (count(res.begin(), res.end(), *it) != 1) {
    //         it = res.erase(it);
    //     } else {
    //         it++;
    //     }
    // }
    // vector<int> dp_up(res.size(), 1), dp_down(res.size(), 1);
    // for(int i = 1, j = res.size()-2; i < res.size(); i++, j--)
    // {
    //     for(int k = 0; k < i; k++)
    //     {
    //         if(res[i] > res[k])
    //         {
    //             if(dp_up[k] + 1 > dp_up[i])
    //             dp_up[i] = dp_up[k]+1;
    //         }
    //     }
    //     for(int k = res.size()-1; k > j; k--)
    //     {
    //         if(res[j] > res[k])
    //         {
    //             if(dp_down[k] + 1 > dp_down[i])
    //             dp_down[j] = dp_down[k]+1;
    //         }
    //     }
    // }
    // vector<int> dp(res.size(), 0);
    // for(int i = 0; i < dp.size(); i++)
    // {
    //     dp[i] = dp_up[i] + dp_down[i] - 1;
    // }
    // int ans = N-dp[0];
    // for(int i : dp)
    // {
    //     if(N-i < ans)
    //     ans = N-i;
    // }
    // 设置两个dp数组
    int i, j, n = N;
    vector<int>heights(res );
    vector<int> dp_h(n, 1), dp_t(n, 1);
    // 正序遍历
    for (i = 0; i < n; i++) {
        for (j = 0; j < i; j++) {
            if (heights[i] > heights[j]) {
                dp_h[i] = max(dp_h[i], dp_h[j] + 1);
            }
        }
    }
    // 逆序遍历
    for (i = n - 1; i >= 0; i--) {
        for (j = n - 1; j > i; j--) {
            if (heights[i] > heights[j]) {
                dp_t[i] = max(dp_t[i], dp_t[j] + 1);
            }
        }
    }
    // 求和得到最长先增后减子序列的长度
    int maxNum = 0;
    for (i = 0; i < n; i++) {
        if (dp_t[i] + dp_h[i] - 1 > maxNum)
            maxNum = dp_t[i] + dp_h[i] - 1;
    }
    // 输出
    cout << n - maxNum << endl;
    // cout << ans;
}
// 64 位输出请用 printf("%lld")