洛谷 1091. 合唱队形
原题链接
简单
作者:
czawa
,
2021-10-04 19:25:40
,
所有人可见
,
阅读 197
/*
* 额就是一个最长上升子序列和最长下降子序列,O(n^2)的时间复杂度预处理出来,然后暴力的求解最大值就可以了。
* 或者暴力枚举每一个点,然后O(nlogn)的求出最长上升子序列和最长下降子序列,时间复杂度O(n^2log N)
*/
#include <bits/stdc++.h>
using namespace std;
int f[100010];
int a[100010];
int g[100010];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
scanf ("%d", &a[i]);
for (int i = 1; i <= n; i ++) {
f[i] = g[i] = 1;
for (int j = 1; j < i; j ++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i >= 1; i --)
for (int j = i + 1; j <= n; j ++)
if (a[j] < a[i])
g[i] = max(g[i], g[j] + 1);
int mx = 0;
for (int i = 1; i <= n; i ++)
mx = max(mx, f[i] + g[i]);
cout << n - mx + 1 << endl;
return 0;
}