题解：P13714 淘汰（Hard ver.）

· · 题解

有可能有用的事实：如果初始 x = 0，只有 \operatorname{or} 操作，那么这个问题相当于子集覆盖，只能做到 O(3^n)。（其实我做的时候没发现这个事实）

容易发现 \operatorname{and},\operatorname{or} 操作本质上是对一个集合进行覆盖（覆盖成 0 或 1），因此我们所做的每一次操作都至少会让一个数归位，而且这个归位的位置上的数后续不会被修改成别的数（否则相当于本次操作被后续的操作完全覆盖）。

那么我们尝试把操作的集合覆盖，改成钦定一个子集归位，尝试做一个 dp。

设 dp_S 表示已经归位了 S 集合内的位置需要的最小代价，考虑假设此时我们要把 S' 集合中的位置归位，不妨设我们用的是 \operatorname{or}，则 S' 中的位置在 y 上都是 1。

考虑这样归位需要满足的条件：

  1. 这个数在 S' 包含的位置上必须都是 1。

  2. 考虑已经归位的那些 0 所在的位置 S_0，这些位置上必须是 0。

设 f_{S_0,S_1} 表示钦定 S_0 这个集合上都是 0，S_1 这个集合上都是 1，其他位置可以填 1 也可以填 0 的所有 \operatorname{or} 操作中权值最小的操作，这个状态可以枚举子集进行转移，但是空间爆了。

我们再回顾一下上面的限制，不难发现，我们的限制实际上只和目标状态有关，比如目标状态有一位是 0，就不可能存在一个限制要求这一位必须是 1。（感性理解一下，因为我们做的操作就是归位）。

因此 f 状态可以改写，改写成 f_S 表示钦定所有 x\in S 位上的数都与目标状态对应的第 x 位相同，其他位任意，的操作中权值最小的操作，这部分预处理可以 O(n2^n) 完成。

此时我们再做 dp_S 的转移就只需要枚举一个子集，复杂度 O(3^n)，常数非常小。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e11;
int n,k,x,y;
int S0,S1;
int a[200005],b[200005],c[200005],d[200005];
int vor[(1<<16)+5],vand[(1<<16)+5];
int dp[(1<<16)+5];
void solve(){
    cin >> n >> k >> x >> y;
    for(int i = 1;i<=n;i++)cin >> a[i];
    for(int i = 1;i<=n;i++)cin >> b[i];
    for(int i = 1;i<=n;i++)cin >> c[i];
    for(int i = 1;i<=n;i++)cin >> d[i];
    for(int i =0 ;i<(1<<k);i++)dp[i] = vor[i] = vand[i] = inf;
    for(int i = 1;i<=n;i++){
        vand[a[i]] = min(vand[a[i]],c[i]);
        vor[b[i]] = min(vor[b[i]],d[i]);
    }
    S1 = y,S0 = (1<<k)-1-y;
    for(int i = 0;i<k;i++){
        for(int j = 0;j<(1<<k);j++){
            if(y>>i&1){
                //限制是选 1，0 加上 1
                if(j>>i&1){
                    vor[j^(1<<i)] = min(vor[j^(1<<i)],vor[j]);
                    vand[j^(1<<i)] = min(vand[j^(1<<i)],vand[j]);
                }
            }else{
                if(j>>i&1){
                    vor[j] = min(vor[j^(1<<i)],vor[j]);
                    vand[j] = min(vand[j^(1<<i)],vand[j]);
                }
            }
        }
    }
    int S = (1<<k)-1-(x^y);
    dp[S] = 0;
    for(int i = 0;i<(1<<k);i++)if((i&S) == i)dp[i] = 0;
    for(int i = 0;i<(1<<k);i++){
        if(dp[i] == inf)continue;
        int s0 = S0&i,s1 = S1&i;
        int T1 = S1-s1,T0 = S0-s0;
        for(int j = T1;j;j = (j-1)&T1){
            dp[i|j] = min(dp[i|j],dp[i]+vor[j|(S0-s0)]);
        }
        for(int j = T0;j;j = (j-1)&T0){
            dp[i|j] = min(dp[i|j],dp[i]+vand[(S0-j)|s1]);
        }
    }
    int res;
    if(dp[(1<<k)-1] == inf)res = -1;
    else res = dp[(1<<k)-1];
    cout << res << '\n';
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//  freopen("P13714_1.in","r",stdin);
    int t;cin >> t;
    while(t--)solve();
}