题解 | #合唱队#C++简洁版DP寻找最大长度

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 3010;

vector<vector<int>> f(N, vector<int> (2, 1)); //初始长度为自身
int n;
int h[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> h[i];
    
    //边界条件
    f[0][0] = f[n+1][0] = 0; //维持边缘队列的队形不需要操作
    
    //DP:
    //1.维持递增队列
    for(int i = 2; i <= n; i++)
        for(int j = 1; j < i; j++)
            if(h[i] > h[j])
                f[i][0] = max(f[i][0], f[j][0] + 1);
    //2.维持递减队列
    for(int i = n - 1; i >= 0; i--)
        for(int j = n; j > i; j--)
            if(h[i] > h[j])
                f[i][1] = max(f[i][1], f[j][1] + 1);
    
    //寻找最大队形长度
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(f[i][0] && f[i][1])
            ans = max(ans, f[i][0] + f[i][1] - 1); //最高点被重复计算一次
        else
            ans = max(ans, f[i][0] + f[i][1]);
        
    }
    cout << n - ans << endl;
    
    return 0;
}