考察点
最长下降子序列
题目分析
根据题意:合唱队形 由中间向两侧 同学的身高逐渐降低
显然,”最中间”的同学 身高最高。
(最中间并不意味着合唱队形关于对他对称 所以加引号)
因此,我们只需要枚举最高身高 ,
以他为原点,向左、向右找最长下降子序列。
最终的长度就是 答案
法1:朴素做法
$O(n^2 log(n))$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
int a[N];
int le[N],ri[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=-1;
for(int i=1;i<=n;i++){ // 枚举最大值:令 a[i] 为最大值
memset(le,0,sizeof le);
memset(ri,0,sizeof ri);
le[1]=ri[1]=a[i];
int ll=1,rr=1;
for(int l=i-1;l>=1;l--) {
if(a[l]<le[ll]) le[++ll]=a[l];
else{
int j=lower_bound(le+1,le+ll+1,a[l],greater<int>())-le; // 找 <= 的
if(j!=1) le[j]=a[l];
}
}
for(int r=i+1;r<=n;r++){
if(a[r]<ri[rr]) ri[++rr]=a[r];
else{
int j=lower_bound(ri+1,ri+rr+1,a[r],greater<int>())-ri; // 找 <= 的
if(j!=1) ri[j]=a[r];
}
}
res=max(ll+rr-1,res);
}
cout<<n-res;
return 0;
}
法2:优化
$O(nlog(n))$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
int h[N];
int f[N],g[N],k[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
k[1]=h[1];
f[1]=1;
int l=1;
for(int i=2;i<=n;i++){ // f[i]:以i点结尾,区间[1,i],最长上升子序列 的长度
if(h[i]>k[l]) k[++l]=h[i],f[i]=l;
else {
int j=lower_bound(k+1,k+l+1,h[i])-k;
k[j]=h[i];
f[i]=j;
}
}
// 上面求出来 f[i],下面求 g[i]
memset(k,0,sizeof k);
g[n]=1;
l=1;
k[1]=h[n];
for(int i=n-1;i>=1;i--){ // g[i]:以i点结尾 , 区间[n,i] (n>=i),最长上升子序列 的长度
if(h[i]>k[l]) k[++l]=h[i],g[i]=l;
else{
int j=lower_bound(k+1,k+1+l,h[i])-k;
k[j]=h[i];
g[i]=j;
}
}
int res=-1;
for(int i=1;i<=n;i++) res=max(res,f[i]+g[i]-1);
cout<<n-res;
return 0;
}