题解 | #合唱队形#

#include<iostream>
#include<algorithm>
using namespace std;
int n,maxsum=0;
int sum[100];
void fun(int a[],int flag){
	int dp[100]={1};
	for(int i=1;i<=n;i++){
	  int max1=1;
	  for(int j=1;j<i;j++){
		if(a[i]>a[j]&&dp[j]+1>max1) max1=dp[j]+1;
	   }
	  dp[i]=max1;
   }
  if(flag==1) reverse(dp+1,dp+n+1);
   for(int i=1;i<=n;i++){
   	 sum[i]+=dp[i];
   	 if(flag==1){
   	 	if(sum[i]>maxsum) maxsum=sum[i];
		}
   }
}
int main(){
	int i,j,max=0;
	int a[100];
	for(i=1;i<=n;i++)cin>>a[i];
    fun(a,0);
    reverse(a+1,a+n+1);
    fun(a,1);
    cout<<n-maxsum+1;
}