题解 | #合唱队#

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

//队形类
class Formation {
  private:
    //人数
    int N;

    //同学们的身高
    vector<int> classmatesHeights;

    //最长递增子序列长度
    vector<int> longestIncSubLen;

    //最长递减子序列长度
    vector<int> longestDecSubLen;

  public:
    //构造函数
    Formation(const int N) {

        //录入数据
        this->N = N;
        this->classmatesHeights.clear();
        for (int i = 0; i < N; i++) {
            int t = 0;
            cin >> t;
            this->classmatesHeights.push_back(t);
        }

        //数组置1
        this->longestIncSubLen.resize(this->N, 1);
        this->longestDecSubLen.resize(this->N, 1);
        return;
    }

    //析构函数
    ~Formation() {
        this->classmatesHeights.clear();
        this->longestDecSubLen.clear();
        this->longestIncSubLen.clear();
        return;
    }

    //在inc[i]处填充末端下标为i的最长递增子序列长度
    void IncLen(void) {

        // 进行判断前，考虑最坏情况，即整体为降序，每个最长递增子序列都只有一个元素
        // 但如果在范围内存在j<i，使得li[j]<li[i]，则可以将下标为i的元素接到末端为li[j]的递增子序列的末端
        // 可得inc[i]=max{inc[i],inc[j]+1}

        // 从头开始遍历
        for (int i = 0; i < this->N; i++)

            //取比i小的j
            for (int j = 0; j < i; j++)

                //如果下标为j的同学身高小于下标为i的同学
                if (this->classmatesHeights[j] < this->classmatesHeights[i]) {
                    int a = this->longestIncSubLen[i];
                    int b = this->longestIncSubLen[j] + 1;
                    this->longestIncSubLen[i] = a < b ? b : a;
                }
        return;
    }

    //填充dec
    void decLen(void) {

        //从尾部开始遍历
        for (int i = this->N - 1; i >= 0; i--)

            //取比i大的j
            for (int j = this->N - 1; j > i; j--)

                //如果下标为j的同学身高小于下标为i的同学
                if (this->classmatesHeights[i] > this->classmatesHeights[j]) {
                    int a = this->longestDecSubLen[i];
                    int b = this->longestDecSubLen[j] + 1;
                    this->longestDecSubLen[i] = a < b ? b : a;
                }
        return;
    }

    //排成合唱队型需要出列的最少人数
    int numOfDequeue(void) {
        this->decLen();
        this->IncLen();

        //最长队列
        int maxLen = 0;
        for (int i = 0; i < this->N; i++) {
            int len = this->longestDecSubLen[i] + this->longestIncSubLen[i] - 1;
            maxLen = maxLen < len ? len : maxLen;
        }
        return this->N - maxLen;
    }
};

int main() {
    int N;
    while (cin >> N) { // 注意 while 处理多个 case
        cout << Formation(N).numOfDequeue() << endl;
    }
}
// 64 位输出请用 printf("%lld")