合唱队

HJ24 合唱队

思路：

找到正序的最长上升子序列和逆序的最长上升子序列，然后确定最长的合唱队形，最后用n - res 就是答案。

代码：

#include<iostream>
using namespace std;
int  n;
const int N = 3010;
int a[N];
int g[N];
int f[N];

int main(){
    cin>>n;
    for(int i = 0; i < n; i++) cin>>a[i];
    for(int i = 0; i < n; i++){
        f[i] = 1;
        for(int j = 0; j <= i; j++){
            if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1);
        }
    }
    
    for(int i = n - 1; i >= 0; i--){
        g[i] = 1;
        for(int j = n - 1; j >= i; j--){
            if(a[i] > a[j]) g[i] = max(g[i],g[j] + 1);
        }
    }
    int res = 0;
    for(int i = 0; i < n; i++) res = max(res,f[i] + g[i] - 1);
    cout<<n - res;
    return 0;
}