题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int h[110];
int f[110], g[110];
int n;
int main (){
cin >> n;
for (int i = 1; i <= n;i++)
cin >> h[i];
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);
}
}
for (int i = n; i;i--){
g[i] = 1;
for (int j = n; j>i;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);
}
cout << n - res << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla