题解 | #合唱队#

C++代码

具体我也是参考别人的代码才写出来的

一维动态规划，就是计算递增子序列的个数和递减子序列的个数，大概思路就是这样的

比如说，我有10个人，ABCDE FGHIJ, 然后创建了vector up(10),down(10)；这两个序列

up[0]就是A，算上它自己就等于1，如果B比它高的话，那么AB就是递增子序列，此时up[1]就加1，等于2

否则up[1]就不变，以此类推

down的话也是这个道理，从最后的一位的J开始，down[9]就是J，算上它自己就是1，如果I比J高，那么down[8]就加一，这样就获得了每个位置的最长递增子序列长度和最长递减子序列长度数目了

比如说，假设E最高，那么在E之前就有up[4]-1个人的身高是递增的，之后就有down[4]-1个人的身高是递减的，那么加上它自己，就有up[4]+down[4]-1个人能够出列作为合唱队，答案呼之欲出。最后返回的数字就是总人数减去合唱队人数

#include<iostream>
#include<vector>

using namespace std;
int func(vector<int> height){//题目的意思是最多可以多少人排列成合唱队
    if(height.empty())return 0;
    int n = height.size();
    vector<int> up(n);//建立递增序列数量的记录
    vector<int> down(n);//建立递减序列数量的记录
    up[0] = 1;
    down[n-1] = 1;
    for(int i = 0; i < n; i++){
        up[i] = 1;
        for(int j = 0; j < i; j++){
            if(height[i] > height[j]){
                up[i] = max(up[j] + 1, up[i]);
            }
        }
    }
    for(int i = n-1; i > -1; i--){
        down[i] = 1;
        for(int j = n-1; j > i; j--){
            if(height[j] < height[i]){
                down[i] = max(down[j] + 1, down[i]);
            }
        }
    }
    int ans = INT8_MIN;
    for(int i = 0; i < n; i++){
        ans = max(ans, up[i] + down[i] - 1);//寻找最多人树的组合
    }
    return n - ans;//返回出列人数
    
}

int main(){
    int N;
    while(cin>>N){
        vector<int> height;
        int h;
        for(int i = 0; i < N; i++){
            cin>>h;
            height.emplace_back(h);
        }
        int num = func(height);
        cout<<num<<endl;
    }
    return 0;
}