AcWing 482. 合唱队形
原题链接
中等
作者:
wjie
,
2021-01-27 11:07:25
,
所有人可见
,
阅读 266
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> vec(n, 0), inc(n, 1), rev_inc(n, 1);
for (int i = 0; i < n; ++i) scanf("%d", &vec[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
if (vec[i] > vec[j])
inc[i] = max(inc[i], inc[j]+1);
reverse(vec.begin(), vec.end());
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
if (vec[i] > vec[j])
rev_inc[i] = max(rev_inc[i], rev_inc[j]+1);
int res = 0;
for (int i = 0; i < n; ++i) res = max(res, inc[i]+rev_inc[n-1-i]-1);
printf("%d", n-res);
return 0;
}