解法一
时间复杂度:$O(n^2)$
可以看出合唱队形最终呈现的是一个峰形,左半部分从前往后做一遍最长上升子序列,右半部分从后往前做一边最长上升子序列,最后枚举分割点即可。
因为 $f[k]$ 和 $g[k]$ 代表的就是以 $k$ 结尾(必定包含 $k$)的最长上升子序列的长度。
可参照 y 总的视频讲解。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N], f[N], g[N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> w[i];
for (int i = 0; i < n; ++i) {
f[i] = 1;
for (int j = 0; j < i; ++j) {
if (w[j] < w[i]) f[i] = max(f[i], f[j] + 1);
}
}
for (int i = n - 1; i; --i) {
g[i] = 1;
for (int j = n - 1; j > i; --j) {
if (w[j] < w[i]) g[i] = max(g[i], g[j] + 1);
}
}
int res = 0;
for (int k = 0; k < n; ++k) res = max(res, f[k] + g[k] - 1);
cout << n - res << endl;
return 0;
}
算法二(不推荐)
时间复杂度:$O(n^3)$
虽说不推荐这种写法,但我想这是大多数人一开始的思路,并且可能会这样写。
因为枚举分割点和求最长上升子序列、最长下降子序列放在了一起,造成了时间复杂度为 $O(n^3)$,其中有一个难点就是 $k$ 必须包含,所以在求最长上升子序列、最长下降子序列时做了一定的改动(在这里也卡了许久)。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int h[N];
int isdown(int l, int r)
{
int mx = 1, f[N];
for (int i = l; i <= r; ++i) {
if (h[i] > h[r] || i == l) f[i] = 1;
else f[i] = 0;
for (int j = l; j < i; ++j) {
if (h[j] > h[i]) f[i] = max(f[i], f[j] + 1);
}
mx = max(mx, f[i]);
}
return mx;
}
int isup(int l, int r)
{
int mx = 1, f[N];
for (int i = l; i <= r; ++i) {
if (h[i] < h[r] || i == r) f[i] = 1;
else f[i] = 0;
for (int j = l; j < i; ++j) {
if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
}
mx = max(mx, f[i]);
}
return mx;
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
int mx = 0;
for (int i = 0; i < n; ++i) {
int r1 = isup(0, i);
int r2 = isdown(i, n - 1);
mx = max(mx, r1 + r2 - 1);
}
cout << n - mx << endl;
return 0;
}