题解 | #[NOIP2004]合唱队形#
[NOIP2004]合唱队形
https://ac.nowcoder.com/acm/problem/16664
合唱队形
链接: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;
}