题解：P10561 [ICPC 2024 Xi'an I] Smart Quality Inspector

· · 题解

题解：P10561 [ICPC 2024 Xi'an I] Smart Quality Inspector

思路

注意到 1\le K\le N\le 20，考虑状态压缩动态规划。\ 可以枚举填入序列的状态 (i)_2，高位表示左边。1 表示已填入数，0 表示未填入数。设 f_i 表示在填入状态为 (i)_2 的情况下的最小代价。\ 我们需要从大到小填数，这样可以保证后填的数不会影响先填的数对答案的贡献，满足无后效性。这样，我们要填的数就是 k-tot(i)+1，其中 tot(i) 表示 (i)_2 中 1 的个数（在代码中，我们可以使用内置函数 __builtin_popcount(i) 来快速计算）。把当前数填入之后，它对答案的贡献就是 x\times[k-tot(i)+1]，其中 x 表示满足区间最大值为 k-tot(i)+1 的合法区间 [l_i,r_i] 数量。设当前填入数位置为 p，左边第一个 1 的位置为 L，右边第一个 1 的位置为 R，则合法区间需要满足 l_i\in(L,p],r_i\in[p,R)。\ 注意到数据范围 1\le M\le 10^5，暴力枚举区间肯定会超时。于是，我们就需要使用二维前缀和快速求出 x。\ 二维前缀和初始化：对于每个 l_i 和 r_i，使 sum_{l_i,r_i}+1；\ 二维前缀和计算公式：sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]；\ 二维前缀和查询公式：x=sum[p][r-1]-sum[p][p-1]-sum[l][r-1]+sum[l][p-1];。\ 那么，转移方程就是：f_i\gets\min\{f_i,f_{i-2^p}+x\times[k-tot(i)+1]\}。最终答案即为所有填入 k 个数字的状态的最小值。

注意点

:::success[AC Code] 时间复杂度 O(n2^n)。

#include<bits/stdc++.h>
using namespace std;
int n,k,m,sum[25][25],f[(1<<20)+1],ans=2e9;
int main(){
    cin>>n>>k>>m;
    for(int i=1;i<=m;++i){
        int l,r;
        cin>>l>>r;
        ++sum[l][r];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; // 二维前缀和计算
        }
    }
    for(int i=1;i<(1<<n);++i){
        int tot=__builtin_popcount(i);
        if(tot>k)continue; // 填入数量过多，跳过
        f[i]=INT_MAX; // 一定要初始化成极大值！
        for(int j=1;j<=n;++j){
            if(!((i>>j-1)&1))continue;
            int l,r;
            for(l=j+1;l<=n;++l){
                if((i>>l-1)&1)break;
            }
            for(r=j-1;r>=1;--r){
                if((i>>r-1)&1)break;
            }
            l=n+1-l;
            r=n+1-r;
            int p=n+1-j;
            int x=sum[p][r-1]-sum[p][p-1]-sum[l][r-1]+sum[l][p-1]; // 合法区间个数
            f[i]=min(f[i],f[i-(1<<j-1)]+x*(k-tot+1));
        }
    }
    for(int i=1;i<(1<<n);++i){
        if(__builtin_popcount(i)==k){ // 计算答案
            ans=min(ans,f[i]);
        }
    }
    cout<<ans;
    return 0;
}

:::