dp-合唱隊問題

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int someman(vector<int> &heights){
    int n = heights.size();
    vector<int> dp1(n,1);
    vector<int> dp2(n,1);
    for(int i = 0;i <= n;i++){
        for(int j = 0;j < i;j++){
            if(heights[j] <= heights[i]){
                dp1[i]= max(dp1[j]+1,dp1[i]);
            }
            
        }
    }
    for(int i = n-1;i >= 0 ;i--){
        for(int j = n-1;j > i;j--){
            if(heights[j] <= heights[i]){
                dp2[i]= max(dp2[j]+1,dp2[i]);
            }
            
        }
    }
    return (n - (*min_element(dp1.begin(),dp1.end()) +*min_element(dp2.begin(),dp2.end())));
}
int main(void){
    vector<int> heights={186, 186, 150, 200, 160, 130, 197, 220};
    int n = someman(heights);
    printf("出列:%d",n);
    return 0;
}