合唱队

#include <bits/stdc++.h>
using namespace std;
//这题采用的是动态规划的思想，但是我已开始没有思路，后来看了评论区的思路后，才重新写的
//然后，无意中容易犯一个错误：题目问的是需要去掉几个人，而动态规划求出的两个标记数组则是表示合唱团剩余的人数！！！
//从左向右或从右向左标记的代码值得铭记！！！别试图用O(n)的方式求解，至少目前没想到也没看到~
 int main(){
    int i, j, t, n;
    vector<int> vi, fgL, fgR;
    while(scanf("%d", &n) != EOF){
        vi.clear();
        fgL = vector<int>(n, 1); //初始状态
        fgR = vector<int>(n, 1);
        for(i=0; i<n; i++){
            scanf("%d", &t);
            vi.push_back(t);
        }
　　　　　//状态转移
        for(i=1; i<n; i++){ //从左向右遍历
            for(j=i-1; j>=0; j--){
                if(vi[i]>vi[j] && fgL[j]>=fgL[i]) fgL[i] = fgL[j] + 1;
            }
        }
        for(i=n-2; i>=0; i--){ //从右向左遍历
            for(j=i+1; j<n; j++){
                if(vi[i]>vi[j] && fgR[j]>=fgR[i]) fgR[i] = fgR[j] + 1;
            }
        }
        t = 0;
        for(i=0; i<n; i++) if(fgL[i]+fgR[i] > t) t = fgL[i] + fgR[i];
        printf("%d\n", n+1-t); //这里实际为n-(t-1) t-1的原因是第 i 个位置重复统计了！
    }
    return 0;
}