题解 | #合唱队#

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

int main() {
    int N;
    cin >> N; // 注意 while 处理多个 case
        vector<int> height(N, 0);
        // 排除身高相等的人，记录剩下人数
        int K = 0; // 排除的人数
        int h;
        int n = 0;
        while (cin >> h) {
            if (n != 0 && h == height[n-1]) {
                N--;
                K++;
            } else {
                height[n] = h;
                n++;
            }
        }

        vector<int> dp_left(N, 0);
        vector<int> dp_right(N, 0);

        for (int i = 1; i <= N - 2; i++ ) {
            dp_left[i] = i;
            for (int j = i - 1; j >= 0; j--) {
                if (height[i] > height[j]) {
                    if (dp_left[j] + (i - j) - 1 < dp_left[i]) { // 注意距离要减1
                        dp_left[i] = dp_left[j] + (i - j) - 1;
                    }
                } 
            }
        }

        for (int i = N - 2; i >= 1; i--) {
            dp_right[i] = N - 1 - i;
            for (int j = i + 1; j <= N - 1; j++) {
                if (height[i] > height[j]) {
                    if (dp_right[j] + (j - i) - 1 < dp_right[i]) { // 注意距离要减1
                        dp_right[i] = dp_right[j] + (j - i) - 1;
                    }
                }
            }
        }

        int res = dp_left[1] + dp_right[1];
        for (int i = 1; i < N - 1; i++) {
            res = min(res, dp_left[i] + dp_right[i]);
        }
        cout << res + K << endl;
    
    return 0;
}
// 64 位输出请用 printf("%lld")