题解C++ | #合唱队#

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

int main() {
    int n = 0, x = 0;
    cin >> n;
    cin.get();
    vector<int> ns(n);
    for (int i = 0; i < n; i++)
        cin >> ns[i];

    vector<int> dppre(n);
    vector<int> dpend(n);
    
    for (int i = 0; i < n; i++)
    {
        dppre[i] = 1;
        for (int j = 0; j <= i; j++)
        {
            if (ns[i] > ns[j])
            {
                dppre[i] = max(dppre[j]+1, dppre[i]);
            }
        }
    }

    for (int i = n-1; i >= 0; i--)
    {
        dpend[i] = 1;
        for (int j = n -1; j >= i; j--)
        {
            if (ns[i] > ns[j])
            {
                dpend[i] = max(dpend[j]+1, dpend[i]);
            }
        }
    }

    int result = 0;
    for (int i = 0; i < n; i++)
    {
        result = max(dppre[i]+dpend[i]-1, result);
    }

    cout << n - result << endl;
}
// 64 位输出请用 printf("%lld")