题解 | #合唱队#

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

int main() {
    int N;
    cin >> N;
    vector<int> tall(N);
    for(int i=0;i<N;++i){
        cin >> tall[i];
    }
    vector<vector<int>> dp(N,vector<int>(2,1));
    for(int i=0;i<N;++i){
        for(int j=0;j<i;++j){
            if(tall[i]>tall[j])
                dp[i][0]=max(dp[i][0],dp[j][0]+1);
        }
    }
    for(int i=N-1;i>=0;--i){
        for(int j=N-1;j>i;--j){
            if(tall[i]>tall[j])
                dp[i][1]=max(dp[i][1],dp[j][1]+1);
        }
    }
    int m=N;
    for(int i=0;i<N;++i){
        if(N+1-dp[i][0]-dp[i][1]<m)
            m=N+1-dp[i][0]-dp[i][1];
    }
    cout << m;
}
// 64 位输出请用 printf("%lld")

实际上是两个最长递增序列。

一个最长递增序列从左向右；一个从右向左。

维持两个dp数组，dp[i][0]和dp[i][1]分别保存在两个序列中以i为结尾的最长递增序列的长度。

需要出列的学生为N+1-dp[i][0]-dp[i][1]