合唱队形题解

题目大意：
要求你不改变同学们的站位，删去几位同学，使得该队列中同学的身高先上升，后下降。可以理解为这样：

可以发现，当最高的同学为 $i$ (索引，后面不在重复) 时，合唱队形的长度就是从 $1$ 到 $i$ 的最长上升子序列长度与 $i-1$ 到 $n$ 的最长下降子序列的和。
我们可以这么想：先计算出这个队列的最长上升子序列和最长下降子序列（dp数组分别用 lis 和 lds 表示）。之后从 $1$ 开始遍历，取当前值为 $i$ 。那么这时的合唱队形长度就是 $lis_i + lds_i -1$ 。我们取遍历中合唱队形长度的最大值，与同学总数相减。即为最少出列次数。
代码示例，注意最长下降子序列是倒着求的，既从 $n$ 到 $1$ （索引）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int a;
    cin >> a;
    int ans=0;//最长合唱队形长度
    int sz[1005]={},lis[1005]={},lds[1005]={};
    for(int i=1;i<=a;i++){
        cin >>sz[i];
    }for(int i=1;i<=a;i++){\\lis
        lis[i]=1;
        for(int j=1;j<i;j++){ 
            if(sz[j]<sz[i]){
                lis[i]=max(lis[i],lis[j]+1);
            }
        }
    }
    for(int i=a;i>=1;i--){\\lds
        lds[i]=1;
        for(int j=a;j>i;j--){
            if(sz[j]<sz[i]){
                lds[i]=max(lds[i],lds[j]+1);
            }
        }ans=max(lis[i]+lds[i]-1,ans);
    }cout << a-ans;
    return 0;
}