题解 | #合唱队#
合唱队
http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
看了大佬们的题解才写出来的，最长子序列··
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin>>n){
vector<int> dp1(n,1);
vector<int> dp2(n,1);
vector<int> height(n,0);
for(int i=0;i<n;++i){
cin>>height[i];
}
//由左向右最长子序列
for(int i=0;i<n;++i){
for(int j=0;j<i;j++){
if(height[i]>height[j])
dp1[i]=max(dp1[i],dp1[j]+1);
}
}
//由右向左
for(int i=n-1;i>=0;--i){
for(int j=n-1;j>i;--j){
if(height[i]>height[j])
dp2[i]=max(dp2[i],dp2[j]+1);
}
}
int max_m=0;
for(int i=0;i<n;++i){
if(dp1[i]+dp2[i]-1>max_m)
max_m = dp1[i]+dp2[i]-1;
}
cout<<n-max_m<<endl;
}
return 0;
}
