题解 | 合唱队

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int h[N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    vector<int> f(N,0);
    vector<int> dp(N,0);
    for(int i=1;i<=n;i++)
    {f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(h[i]>h[j])
            {
               f[i]=max(f[i],f[j]+1);//模板，最长上升子序列
            }
        }
    }
    for(int i=n;i>=1;i--)
    {dp[i]=1;
        for(int j=n;j>i;j--)
        {
            if(h[i]>h[j])
            {
                dp[i]=max(dp[i],dp[j]+1);//下降
            }
        }
    }
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        mx=max(mx,f[i]+dp[i]-1);
    }
    cout<<n-mx<<endl;
}

#牛客春招刷题训练营#https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2Fdiscuss%2F726480854079250432

//这题是典中典，是一个dp的简单题，对，模板题。

//上升子序列跟下降子序列的和-1就是最大的队伍长度，最后别忘了答案是n-mx,是我要删去的人数。

//这里的f是上升的写法，dp是下降的写法，为什么要减1呢？因为他俩共同占了一个位置