题解：P1091 [NOIP 2004 提高组] 合唱队形

本题解提供英文和中文两种语言。
This solution is available in both English and Chinese.

中文版本

我们采用预处理的思路，做出两个方向（左到右和右到左）的最长上升子序列。然后再扫描一遍下标，对于每一个下标计算左到右方向的最长上升子序列长度加上右到左方向的最长上升子序列长度再减一（这里的减一是因为中间枚举的下标重复了两次），将所有计算出来的值取最大值，拿总数减去就是答案了。

下面我们来推理一下动态规划的转移方程（从左到右为例）：

f_i = \max_{j = 1}^{i - 1} {f_j + 1}

再考虑一下初始条件，就是把整个 f 数组都初始化为 1 即可。从右到左是同样的道理，就不多叙述了。

代码在尾言前面。

English version

We use the preprocessing idea to make the longest ascending subsequence in two directions (left-to-right and right-to-left). Then scan the subscript again, calculate the longest ascending subsequence length in the left to right direction for each subscript plus the longest ascending subsequence length in the right to left direction and subtract one (minus one here because the subscript of the middle enumeration is repeated twice), take all the calculated values to the maximum, subtract the total number to give the answer.

Let's reason about the transition equation of dynamic programming (from left to right for example) :

f_i = \max_{j = 1}^{i - 1} {f_j + 1}

Consider the initial condition, which is to initialize the entire f array to 1. From the right to the left is the same, not to elaborate.

Below is the C++ code.

代码实现 Code implementation

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 100 + 10;
int n, ans, a[maxn], f[maxn], g[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    fill(&f[0], &f[maxn-1], 1);
    fill(&g[0], &g[maxn-1], 1);
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j < i; j++) 
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j < i; j++) 
            if (a[j] < a[i]) g[i] = max(g[i], g[j] + 1);
    for (int i = 1; i <= n; i++) ans = max(ans, f[i] + g[n - i + 1] - 1);
    cout << n - ans << "\n";
    return 0;
}

尾言 Epilogue

如果

n

再变大，比如到

10^6

，就只能采用

O(n \log n)

的思路了，在这里提供两种：

单调队列 + 二分
线段树维护

我会把第一种思路的代码放在文章末。

n

becomes larger, such as

10^6

, you can only use the idea of

O(n \log n)

, here provide two solutions:

Monotonic queue + binary search
Segment tree maintenance

I'll leave the code for the first idea below.

CPP

#include <bits/stdc++.h>
const int maxn = 3e5 + 10;
using namespace std;
int n, a[maxn], f[maxn], l[maxn], r[maxn], ans = 1, cnt;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    f[1] = a[1]; l[1] = 1;
    for (int i = 2; i <= n; i++) {
        int ll = 1, rr = ans;
        while (ll <= rr) {
            int mid = (ll + rr) >> 1;
            if (a[i] <= f[mid]) rr = mid - 1;
            else ll = mid + 1;
        }
        f[ll] = a[i];
        if (ll > ans) ans++;
        l[i] = ll;
    }
    memset(f, 0, sizeof(f));
    reverse(a + 1, a + n + 1);
    f[1] = a[1]; r[1] = 1; ans = 1;
    for (int i = 2; i <= n; i++) {
        int ll = 1, rr = ans;
        while (ll <= rr) {
            int mid = (ll + rr) >> 1;
            if (a[i] <= f[mid]) rr = mid - 1;
            else ll = mid + 1;
        }
        f[ll] = a[i];
        if (ll > ans) ans++;
        r[i] = ll;
    }
    for (int i = 1; i <= n; i++) cnt = max(cnt, l[i] + r[n - i + 1] - 1);
    cout << n - cnt << "\n";
    return 0;
}

这个代码明显快得多。
This code seems faster than the first one.

题解：P1091 [NOIP 2004 提高组] 合唱队形

文章操作