题解 | 合唱队

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int In[4000];
int De[4000];
int InCr(vector<int> h, int index) {
    int max = 0;
    for (int i = 0; i < index; ++i) {
        if (h[i] < h[index]) {
            if(In[i] == -1)
                In[i] = InCr(h, i);
            int temp = In[i] + 1;
            if (temp > max)
                max = temp;
        }
    }
    return max;
}
int DeCr(vector<int> h, int index) {
    int max = 0;
    for (int i = index + 1; i < h.size(); ++i) {
        if (h[i] < h[index]) {
            if(De[i] == -1)
                De[i] = DeCr(h, i);
            int temp = De[i] + 1;
            if (temp > max)
                max = temp;
        }
    }
    return max;
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < 4000; ++i)
        In[i] = -1, De[i] = -1;
    vector<int> h;
    for (int i  = 0; i < n; ++i) {
        int temp;
        cin >> temp;
        h.push_back(temp);
    }
    int min = 4000;
    for (int i = 0; i < n; ++i) {
        int left = InCr(h, i);
        int right = DeCr(h, i);
        int length = left + right + 1;
        int Out = n - length;
        if (Out < min)
            min = Out;
    }
    cout<<min;
}
// 64 位输出请用 printf("%lld")