题目描述
blablabla
样例
blablabla
//三、合唱队列
/*
这道题的重点在于思路:
先从计算从1开始的最大上升子序列,再计算从n到1的最大下降子序列。
$$$这里需要注意的是:必须要按照顺序来执行,如果从i=1开始寻找最大的下降子序列的话,前面的数组元素还未更新,因此的出来的数据是错误的
*/
#include<iostream>
using namespace std;
const int N = 101;
int h[N], l[N];
int a[N];
int main() {
int n;
cin >> n;
int mx = 1;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)
{
h[i] = 1;
for (int j = 1; j <= i; j++) if (a[i] > a[j])h[i] = max(h[i], h[j] + 1);
}
for (int i = n; i >= 1; i--)
{
l[i] = 1;
for (int j = n; j >= i; j--) if (a[i] > a[j])l[i] = max(l[i], l[j] + 1);
}
for (int i = 1; i <= n; i++)mx = max(mx, h[i] + l[i] - 1);
cout << (n - mx);
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla