题解：CF1367F2 Flying Sort (Hard Version)

· · 题解

简化题意

选择一个最长的不降子序列满足剩下的数要么大于所选序列的最大值要么小于所选序列的最小值。

思路

简单版题解。

和简单版的区别在于原序列元素可重。

沿用简单版的思路，我们仍然对答案序列的最后一位讨论。

考虑到题意要求，我们大致可以将答案序列分为 3 种情况：

那么我们设 dp_{i,0/1/2} 分别表示以 a_i 为结尾的答案序列且只有一种元素 / 正在选择元素并拼接到之前答案序列 / 后缀元素全部出现的序列。

设 lst_{a_i} 表示 a_i 上一次出现的位置，L_{a_i} 表示 a_i 第一次出现的位置，R_{a_i} 表示 a_i 最后一次出现的位置，val_{a_i} 表示 a_i 在原序列中出现的次数。

于是便有转移：

dp_{i, 0} = dp_{lst_{a_i}, 0} + 1\\ dp_{i, 0} = \max \{ dp_{lst_{a_i}, 1}, dp_{lst_{a_i - 1}, 0}, dp_{lst_{a_i- 1}, 2} \} + 1\\ dp_{i, 2} = [i = R_{a_i}] \times dp_{L_{a_i}, 1} + val_{a_i} - 1

每次动态维护 lst_{a_i} 即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int T, n, a[N], L[N], R[N], lsh[N], lst[N], val[N], dp[N][3];

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> T;

    while(T --) {
        for(int i = 1 ; i <= n ; ++ i)
            a[i] = L[i] = R[i] = lsh[i] = lst[i] = val[i] = dp[i][0] = dp[i][1] = dp[i][2] = 0;

        cin >> n;
        for(int i = 1 ; i <= n ; ++ i)
            cin >> a[i], lsh[i] = a[i];

        sort(lsh + 1, lsh + 1 + n);

        int tot = unique(lsh + 1, lsh + 1 + n) - lsh - 1;

        for(int i = 1 ; i <= n ; ++ i)
            a[i] = lower_bound(lsh + 1, lsh + 1 + tot, a[i]) - lsh;

        for(int i = 1 ; i <= n ; ++ i) {
            if(! L[a[i]]) L[a[i]] = i;

            ++ val[a[i]];
        }

        for(int i = n ; i ; -- i)
            if(! R[a[i]]) R[a[i]] = i;

        for(int i = 1 ; i <= n ; ++ i) {
            dp[i][0] = dp[lst[a[i]]][0] + 1;
            dp[i][1] = max({dp[lst[a[i]]][1], dp[lst[a[i] - 1]][0], dp[lst[a[i] - 1]][2]}) + 1;
            if(i == R[a[i]]) dp[i][2] = dp[L[a[i]]][1] + val[a[i]] - 1;

            lst[a[i]] = i;
        }

        int ans = 0;

        for(int i = 1 ; i <= n ; ++ i)
            for(int j = 0 ; j <= 2 ; ++ j)
                ans = max(ans, dp[i][j]);

        cout << n - ans << '\n';
    }

    return 0;
}