题解 | 合唱队形

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  思路：左边前缀最长递增，右边后缀最长递减，然后枚举每个点找出最大的递增+递减-1；（思路来自题解）
//  题目看错了，我以为最高的要在中间
#include <iostream>
#include <vector>
using namespace std;

vector<int> abc(1010, 1), cba(1010, 1), a(1010);//------abc记录递增，cba记录递减，a记录输入
int main() {
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  int n;
  cin >> n;
  cin >> a[0];
  for (int i = 1; i < n; i++){//--------输入，同时维护abc
    cin >> a[i];
    for (int j = 0; j < i; j++){
      if (a[j] < a[i]) abc[i] = max(abc[i], abc[j] + 1);
    }
  }
  for (int i = n - 1; i >= 0; i--){//-----------处理cba
    for (int j = n - 1; j > i; j--){
      if (a[j] < a[i]) cba[i] = max(cba[i], cba[j] + 1);
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++){//----------枚举
    ans = max(abc[i] + cba[i] - 1, ans);
  }
  cout << n - ans;//------------记得题目要的是最少出列几个人，要用n减
}
// 64 位输出请用 printf("%lld")