描述

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设KK位同学从左到右依次编号为 1，2…，K ，他们的身高分别为T_1,T_2,…,T_KT1,T2,…,TK ，若存在i(1\leq i\leq K)i(1≤i≤K) 使得T_1<T_2<......<T_{i-1}<T_iT1<T2<......<Ti−1<Ti 且 T_i>T_{i+1}>......>T_KTi>Ti+1>......>TK，则称这KK名同学排成了合唱队形。
通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

数据范围： 1≤n≤3000 

输入描述：

用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输出描述：

最少需要几位同学出列

示例1

输入： 
8
186 186 150 200 160 130 197 200
输出： 
4
说明： 
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
代码部分：
#include<stdio.h>
//以下Senky的代码：
//因为一定能组成合唱团：
//总人数-最多组成合唱团需要的人数=最少组成合唱团需要的人数
int max(int x, int y) { //返回最大值的函数
    return (x > y) ? x : y;
}

void start() {
    int n;//n个同学
    while (~scanf("%d", &n)) {
        int str[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &str[i]); //把同学的身高放入数组
        }
        int dp_left[n];//从左往右以第i个同学的身高作为结尾的同学的人数
        int dp_right[n];//从右往左以第i个同学的身高作为结尾的同学的人数
        int ret[n];//ret[i]存储以i为最高的同学，最终合唱队最多要多少人
        int maxnum=0;//记录ret[n]中最多需要组成合唱团的人数

        dp_left[0] = 1; //最少一个人
        dp_right[n - 1] = 1; //最少一个人
        //从左往右以第i个同学的身高作为结尾的同学的人数
        for (int i = 1; i < n; i++) {
            dp_left[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
            if (str[i] > str[j]) dp_left[i] = max(dp_left[i], dp_left[j] + 1);
            }
        }

        //从右往左以第i个同学的身高作为结尾的同学的人数
        for (int i = n - 2; i >= 0; i--) {
            dp_right[i] = 1;
            for (int j = i + 1; j < n; j++) {
            if (str[i] > str[j]) dp_right[i] = max(dp_right[i], dp_right[j] + 1);
            }
        }

        for(int i=0;i<n;i++){//以i作为最高的同学的合唱队序列最多为ret[i]人
            ret[i]=dp_left[i]+dp_right[i]-1;//以i最高的在两个数组中都算了故减去
        }

        for(int j=0; j<n-1; j++){
            maxnum=max(maxnum,ret[j]>ret[j+1]?ret[j]:ret[j+1]);//求最多组成的人数
        }

        printf("%d",n-maxnum);//总人数减最多就是最少组成合唱队的人数
    }
}
int main() {
    start();
    return 0;//编辑于2022/10/13
}
图解：

总结：
①刚开始用动态规划的方法，方法挺好用的，就是算法有点难想；
②当前帖子仅供自我精进、学习使用，有不足之处欢迎指正