题解 CF1730F 【Almost Sorted】

Leasier · 2023-09-26 08:07:07 · 题解

与 NOI2023 D1T2 有点像。

没能一眼秒被 goujingyu 嘲讽了 /dk

考虑钦定一个填入 q_i 的顺序——比如说按 p_{q_i} 从小到大填入。

考虑我们对 q_i 的限制，可得：

或言：

• 当前要填入的 p_{q_i} \geq 已填入的最大 p_{q_j} - k。
• 当前要填入的 p_{q_i} \leq 未填入的最小 p_{q_j} + k。

注意到 k 很小，感性理解可以发现此时前面有一大堆都已填入。

具体的，当考虑换一种描述方式：

• 设 [1, x] 中的数都已填入。
• 当前要填入的数 \in [x + 1, x + k + 1]。

考虑状压 dp，设 dp_{i, S} 表示 [1, i] 中的数都已填入，i + 1 未填入，[x + 1, x + k + 1] 中数的填入信息为 S。

枚举填入哪个并暴力维护逆序对即可。时间复杂度为 O(n^2 + nk 2^k)。

代码：

#include <stdio.h>

int pos[5007], dp[5007][517], sum[5007];

inline int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int n, k, full;
    scanf("%d %d", &n, &k);
    k++;
    full = (1 << k) - 1;
    for (int i = 1; i <= n; i++){
        int p;
        scanf("%d", &p);
        pos[p] = i;
    }
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= full; j++){
            dp[i][j] = 0x7fffffff;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i <= n; i++){
        if (i > 0){
            for (int j = 1; j <= pos[i]; j++){
                sum[j]++;
            }
        }
        for (int j = 0; j <= full; j += 2){
            if (dp[i][j] != 0x7fffffff){
                for (int x = 1; x <= k && i + x <= n; x++){
                    if (!(j >> (x - 1) & 1)){
                        int p = i, q = j | (1 << (x - 1)), cnt = sum[pos[i + x] + 1];
                        while (q & 1){
                            p++;
                            q >>= 1;
                        }
                        for (int y = 1; y <= k; y++){
                            if ((j >> (y - 1) & 1) && pos[i + y] > pos[i + x]) cnt++;
                        }
                        dp[p][q] = min(dp[p][q], dp[i][j] + cnt);
                    }
                }
            }
        }
    }
    printf("%d", dp[n][0]);
    return 0;
}