题解 | 合唱队形

//从左向右看，1至i为递增序列，从右向左看，从k至i为递增序列，两者之和减一为总序列长度，
//分别计算位置i处的递增序列与递减序列，相加减一得到最大值
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=100;
int dp1[MAXN];
int dp2[MAXN];
int arr[MAXN];
int ans[MAXN];
int Function(int n){
    for(int i=0;i<n;i++){
        dp1[i]=1;
        for(int j=0;j<i;j++){
            if(arr[i]>arr[j])
            dp1[i]= max(dp1[j]+1,dp1[i]);
        }
    }
    for(int i =n-1;i>=0;i--){
        dp2[i]=1;
        for(int j =n-1;j>i;j--){
            if(arr[i] >arr[j]){
                dp2[i] =max(dp2[j] +1,dp2[i]);
            }
        }
    }
    int answer=0;
    for(int i=0;i<n;i++){
        ans[i] =dp1[i]+dp2[i]-1;//重合点i，故减一；
        answer =max(ans[i],answer);
    }
    answer = n-answer;
    return answer;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    cout<<Function(n)<<endl;
    return 0;
}