合唱队形

思路：

动态规划：正反两次运用LIS
求出以每一个点结尾的从前往后最长递增子序列
以每一个结点结尾的从后往前最长递增子序列
当最大时，记作，表示剩下的同学排成合唱队形最多的人数
则有为当前状态下最少需要出列的同学人数（因为i这个位置被重复计算了一次，故需要+1）

代码：

/*
LIS最长递增子序列
状态方程：
dp[i] = max{dp[i], dp[j] + 1} j <= i && A[j] < A[i]
边界：
dp[i] = 1(1 <= i <= n)
*/
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 300;

int main(){
    int n;
    while(~scanf("%d", &n)){
        int dp1[maxn];//左边最大升序子序列的长度
        int dp2[maxn];//右边最长降序子序列的长度
        int A[maxn];        
        for(int i = 0; i < n; i++){
            scanf("%d", &A[i]);//输入
        }

        /*从前往后寻找以i点为尾的最长递增子列*/
        for(int i = 0; i < n; i++){
            dp1[i] = 1;/*每点为尾的子列长度最小都为1*/
            for(int j = 0; j < i; j++){
                if(A[j] < A[i]){
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }   
        }

        /*从后往前寻找以i点为尾的最长递增子列*/
        for(int i = n - 1; i >= 0; i--){
            dp2[i] = 1;/*每点为尾的子列长度最小都为1*/
            for(int j = n - 1; j > i; j--){
                if(A[j] < A[i]){
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }

        int ans = 1;
        /*寻找点i两个子列和的最大值*/
        for(int i = 0; i < n; i++){
            if(dp1[i] + dp2[i] > ans){
                ans = dp1[i] + dp2[i];
            }
        }
        printf("%d\n", n - ans + 1);//重复减了自身两次，故加1

    }
    return 0;
}