AcWing 482. 合唱队形
原题链接
中等
作者:
wyf
,
2021-01-27 11:29:49
,
所有人可见
,
阅读 298
线性DP:根据题意可知,我们只需要枚举每一数让其为最高峰,往左侧做最长递减数列往右侧做最长递减数列即可,但实际上我们不需要这样做,只需要将数列预处理出,以每个点为终点左侧的最长上升子序列的最大长度,和以该点为终点右侧的最长下降子序列的最大长度,最后枚举每一个点,让其f[i]+g[i],此时我们会多算一个该点,因为每次算最长子序列该点都是包含在内的,故最后要减1,那么按此枚举,最后输出n-res即可,题目中要求是出队列的人数
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N=110;
int q[N];
int f[N],g[N];//f[i]表示最长上升子序列 g[i]表示最长下降子序列
int res;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>q[i];
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(q[i]>q[j])f[i]=max(f[i],f[j]+1);
}
}
for(int i=n;i;i--){
g[i]=1;
for(int j=n;j>i;j--){
if(q[i]>q[j])g[i]=max(g[i],g[j]+1);
}
}
for(int i=1;i<=n;i++)res=max(res,f[i]+g[i]-1);
cout<<n-res<<endl;
return 0;
}