AcWing 482. 合唱队形
原题链接
中等
作者:
回头不是从前
,
2021-01-27 15:51:40
,
所有人可见
,
阅读 299
最长上升子序列
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int d[N], pre[N], post[N];
int n;
int main() {
cin >> n;
for(int i = 0; i < n; ++i) cin >> d[i];
for(int i = 0; i < n; ++i) {
pre[i] = 1;
post[n - i - 1] = 1;
for(int j = 0; j < i; j ++) {
if(d[j] < d[i]) pre[i] = max(pre[i], pre[j] + 1);
}
for(int j = n - 1; j > n - i - 1; --j) {
if(d[j] < d[n - i - 1]) post[n - i - 1] = max(post[n - i - 1], post[j] + 1);
}
}
int res = 0;
for(int i = 0; i < n; ++i) res = max(res, pre[i] + post[i] - 1); // 第i个点重复一次
cout << n - res;
return 0;
}