题解 | #合唱队形#

最长“山顶”子序列

DP：分别递推以s[i]开头的最长下降子序列、以s[i]结尾的最长上升子序列

#include<iostream>
#include<cstring>
using namespace std;

const int maxn=101;

int s[maxn];
int high[maxn];//上升子序列长度
int low[maxn];//下降子序列长度

int student(int n){//“山顶”子序列最大长度
    fill(high,high+n,1);
    fill(low,low+n,1);
    
    for(int i=0;i<n;i++){//从前往后：统计以s[i]结尾的最长上升子序列
      for(int j=0;j<i;j++){
        if(s[i]>s[j])high[i]=max(high[i],high[j]+1);
      }
    }
    
    for(int i=n-1;i>=0;i--){//从后往前：统计以s[i]开头的最长下降子序列
      for(int j=n-1;j>i;j--){
        if(s[i]>s[j])low[i]=max(low[i],low[j]+1);
      }
    }
    
    int ans=0;
    for(int i=0;i<n;i++){
        ans=max(ans,high[i]+low[i]-1);
    }
    
  return ans;
}


int main(){
  int n;
  while(scanf("%d",&n)!=EOF){
    for(int i=0;i<n;i++){
      scanf("%d",&s[i]);
    }
    printf("%d\n",n-student(n));
  }
  
  return 0;
}