题解 | #[NOIP2004]合唱队形#

合唱队形

链接：https://ac.nowcoder.com/acm/problem/16664 来源：牛客网

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

做法

要构造一个先递增后递减的序列，那么我们假设最优点为i，i其实就是最长上升子序列的结尾以及严格最长下降子序列的开始，反过来也一样，那么我们正反都跑一遍最长上升子序列，那么这一点的总和就是拼凑起一个这样序列的最多人数。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
int f1[510000];
int f2[510000];
void slove()
{
    int n;
    std::cin>>n;
    std::vector<int> a(n);
    int ans=0;
    for(int i=0;i<n;i++) std::cin>>a[i];
    for(int i=0;i<n;i++)
    {
        f1[i]=1;
        for(int j=0;j<i;j++)
        {          
            if(a[i]>a[j]) f1[i]=std::max(f1[i],f1[j]+1);
            //ans=std::max(ans,f[i]);
        }
    }
    //std::reverse(a.begin(),a.end());
    for(int i=n-1;i>=0;i--)
    {
        f2[i]=1;
        for(int j=i;j<n;j++)
        {          
            if(a[i]>a[j]) f2[i]=std::max(f2[i],f2[j]+1);
            ans=std::max(ans,f2[i]);
        }
    }
    for(int i=0;i<n;i++)
    {
        ans=std::max(ans,f1[i]+f2[i]-1);
    }
    std::cout<<n-ans<<endl;

}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}