AcWing 482. 合唱队形
原题链接
中等
作者:
羊妞
,
2023-08-08 21:18:29
,
所有人可见
,
阅读 55
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n;
int h[N];//存储身高
int f[N], g[N];
//f[i]:以f[i]结尾的最长的上升子序列
//g[i]:以g[i]为起点的最长的下降子序列
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
//f[]
for(int i = 1; i <= n; i++){
f[i] = 1;
for(int j = 1; j < i; j++)
if(h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
}
//g[]
for(int i = n; i; i--){
g[i] = 1;
for(int j = i + 1; j <= n; j++)
if(h[j] < h[i]) g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);
printf("%d\n", n - res);
return 0;
}