[题解] P10561 [ICPC2024 Xi'an I] Smart Quality Inspector

苏联小渣 · 2024-06-13 19:53:04 · 题解

发现 n,k 都很小，考虑状压。

由于我们要求 \max 之和，所以肯定要枚举这个 \max，也就是要钦定加入顺序，不难想到应该从大往小加入，这样每次加入的数都会成为一些区间的 \max。

设 f_{S} 表示已经加入了最大的 |S| 个数，且位置集合为 S 的最小值。考虑枚举最后一个加入的数，位置不妨记为 p，考虑它会成为哪些区间的 \max。容易发现，这些区间应该包含 p 且不包含更先加入的数。设二进制下 S 中 p 左边第一个 1 的位置为 l-1，右边第一个 1 的位置为 r+1，也就是所有满足 l' \in [l,p],r' \in [p,r] 的 [l',r'] 的最大值都是 k-|S|+1。求出贡献区间数，本质上就是子矩形求和，可以通过二维前缀和预处理和查询，然后 dp 的转移也就简单了：

设贡献到的区间数为 x，那么 f_S=\min \{f_{S-2^p}+x \times (k-|S|+1)\}。于是总时间复杂度 O(n2^n)。

Code：

#include <bits/stdc++.h>
using namespace std;
int n, k, m, l, r, ans=1e9, pre[25][25], f[2000010], lst[25], nxt[25];
int main(){
    scanf ("%d%d%d", &n, &k, &m);
    for (int i=1; i<=m; i++){
        scanf ("%d%d", &l, &r);
        pre[l][r] ++;
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            pre[i][j] = pre[i][j] + pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1];
        }
    }
    for (int S=1; S<(1<<n); S++){
        int tot = 0;
        for (int i=0; i<n; i++){
            if ((S >> i) & 1) tot ++;
        }
        if (tot > k) continue;
        f[S] = 1e9, lst[0] = 0, nxt[n+1] = n+1;
        for (int i=0; i<n; i++){
            if ((S >> i) & 1) lst[i+1] = i+1;
            else lst[i+1] = lst[i];
        }
        for (int i=n-1; i>=0; i--){
            if ((S >> i) & 1) nxt[i+1] = i+1;
            else nxt[i+1] = nxt[i+2];
        }
        for (int i=0; i<n; i++){
            if (!((S >> i) & 1)) continue;
            int T = S - (1 << i);
            int st = lst[i], ed = nxt[i+2] - 2;
            int ad = pre[i+1][ed+1] - pre[st][ed+1] - pre[i+1][i] + pre[st][i];
            f[S] = min(f[S], f[T] + ad * (k - tot + 1));
        }
        if (tot == k) ans = min(ans, f[S]);
    }
    printf ("%d\n", ans);
    return 0;
}