CF1730F Almost Sorted 题解

· · 个人记录

传送门： F. Almost Sorted

题目大意：

给定长度为 n 的排列 p_i 和常数 k，一个长度为 n 的排列 q_i 是合法的当且仅当对于任意 1 \le i < j \le n，p_{q_i} \le p_{q_j}+k。求合法的排列的逆序对数的最小值。

看到 k \le 8，八九不离十就是状压 dp。
考虑从 1 至 n 挨个位置填数，注意到我们若在某个位置上填了 i，那么 [1,i-k) 必定在这个位置之前就已经填上了，同理，(i+k,n] 必定还没有填过，现在我们就只需要关心 [i-k,i) \cup (i,i+k] 这 2k 个数的状态，直接设 f_{i,j,S} 表示第 i 位填 j，[j-k,j) \cup (j,j+k] 中填上的数的集合为 S 时的最小逆序对数，看起来状态数达到了 O(n^24^k) 级别，但实际上第 i 位上填的数的范围是 [i-k,i+k]，所以 j 这一维是 O(k) 的，然后 S 这一维中最大的填过的数和最小的没被填过的数的差不应超过 k，搜一下发现只有 1280=5 \times 2^8 种合法的 S，所以状态数只有 O(nk2^k) 级别。

然而常数还是太大了，必须考虑继续优化。

注意到 S 这一维中最大的填过的数和最小的没被填过的数的差不超过 k，最小的没被填过的数说明小于该数的数全部都填上了，同理最大的填过的数说明大于该数的数全部未填，而现在我们就只需要考虑两数之间的 O(k) 个数了，重新设计 dp 状态 f_{i,S} 表示最小的未被填上的数是 i，(i,i+k] 中填上的数的集合为 S 时的最小逆序对数，这时状态数就降到了 O(n2^k) 级别了，转移时选择 [i,i+k] 中一个没被填过的数填上，使用主席树计算其与已经填过的数形成的逆序对数，可在 O(nk2^k(k+\log n)) 时间内解决该问题。

代码：

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

typedef long long ll;
const int MAXN = 5005;
const int Mod = 998244353;

int n, K, p[MAXN], id[MAXN];
int f[MAXN][1 << 8];//f[i][S] 表示未填的数中最小的是 i，(i,i+k] 填的情况为 S 时的最小逆序对数

inline void chkMin(int &a, int b) { if (a > b) a = b; }

int tot, rt[MAXN];

struct node {
    int ls, rs, sum;
} T[MAXN * 15];

void upd(int &p, int vp, int l, int r, int gk) {
    T[p = ++tot] = T[vp];
    T[p].sum++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mid >= gk) upd(T[p].ls, T[vp].ls, l, mid, gk);
    else upd(T[p].rs, T[vp].rs, mid + 1, r, gk);
}

int query(int p, int l, int r, int gl, int gr) {
    if (gl > gr) return 0;
    if (l >= gl && r <= gr || !p) return T[p].sum;
    int mid = (l + r) >> 1, ret = 0;
    if (mid >= gl) ret = query(T[p].ls, l, mid, gl, gr);
    if (mid < gr) ret += query(T[p].rs, mid + 1, r, gl, gr);
    return ret;
}

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        id[p[i]] = i;
        upd(rt[i], rt[i - 1], 1, n, p[i]);
    }

    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;

    for (int i = 1; i <= n; i++)
        for (int S = 0; S < 1 << K; S++) if (f[i][S] < 1e9) {
            int mn = min(K + 1, n + 1 - i);
            for (int j = min(K, n - i); j; j--) if (!(S >> j - 1 & 1)) {
                mn = j;
                int cnt = (id[i] < id[i + j]) + query(rt[id[i + j]], 1, n, i + K + 1, n);
                for (int k = min(K, n - i); k; k--) if (!(S >> k - 1 & 1))
                    cnt += (id[i + k] < id[i + j]);
                chkMin(f[i][S | 1 << j - 1], f[i][S] + cnt);
            }

            int cnt = query(rt[id[i]], 1, n, i + K + 1, n);
            for (int j = min(K, n - i); j; j--) if (!(S >> j - 1 & 1))
                cnt += (id[i + j] < id[i]);
            chkMin(f[i + mn][S >> mn], f[i][S] + cnt);
        }

    printf("%d", f[n + 1][0]);
    return 0;
}