题解 | #合唱队#

这道题题意理解起来容易引起误解，身高最高的不一定在队伍的中央，只要两边有人（即使无人）也满足条件。
题意理解之后，就需要找解题方法，过程抽象为寻找最长单调递增数列以及最长单调递减数列问题，可以用动态规划来求解
设dp1[i]表示到从1~i的最长单调递增数列，动态方程可以表示为
遍历j:i
如果nums[i]>nums[j] dp[i]=max(dp[i],dp[j]+1) ；
该句的意思是，如果位置j的数值比i的值小，存在两种情况，取走位置j,或者不取位置j,如果取走，那么到i最长单调序列的长度是dp[j]+1;如果不取，就保持当前dp[i],选择两者最大值。
同理单调递减也通过这种方式，从后往前递归。
返回值为，总人数减去，某个位置满足左右单调人数之和最多的人数。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N=0;
    while(cin>>N){
        int nums[N];
        for(int k=0;k<N;k++){
            cin>>nums[k];
        }
        vector<int> dp1(N,1);
        vector<int> dp2(N,1);
        for(int i=0;i<N;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp1[i]=max(dp1[i],dp1[j]+1);
                }
            }
        }
        for(int i=N-1;i>-1;i--){
            for(int j=N-1;j>i;j--){
                if(nums[i]>nums[j]){
                    dp2[i]=max(dp2[i],dp2[j]+1);
                }
            }
        }

        int maxres=0;
        for(int i=0;i<N;i++){
            if(dp1[i]+dp2[i]-1>maxres){
                maxres=dp1[i]+dp2[i]-1;
            }
        }
        int ans=N-maxres;
        cout<<ans<<endl;
        }
}