贪心、动态规划

开始就得到了两个思路。

每次贪心能使得全局和减小量最大的操作，由于每个数在最优情况下的减少量每次都只会单调递减，这个思路看起来很对，结果交上去错了。

暴力枚举每个数如何操作，然后跑背包，这个思路肯定对，但是这样共有 $O(n 2^m)$ 个物品，跑分组背包的时间复杂度为 $O(n 2^m k)$ 会爆炸。

实际上这个问题还是不能贪心，考虑二进制数 $11111$，如果可以用 $00111,01011,10101,11110$ 五个数进行操作，两步能得到的最小值就是 $00111 \& 01011 = 00011$，而三步能得到的最小值是 $01011 \& 10101 \& 11110 = 00000$，两步的最优方案无法衍生出三步的最优方案，所以贪心是错的。

设计 $dp_{i,j}$ 为 $a_i$ 经过 $j$ 次操作后最多能减小的大小，直接 $O(n 2^m)$ 搜出所有方案。

在一个数的最优操作方案中，对于整数 $i,j \ (i<j)$ 必然有第 $i$ 次操作的减小量大于等于第 $j$ 次的减小量，差分所有 $dp_{i,j}$ 的第二维得到减小量序列，选择其中最大的 $k$ 个从原序列的和中减去，即为答案。使用 nth_element 函数在 $O(n 2^m)$ 时间复杂度内拿到前 $k$ 大的减小量值。

总体时间复杂度 $O(n 2^m)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,cnt,lim,b[15],sum[1'025],a[100'005],w[10'000'005];
void solution(){
    cin>>n>>m>>k,cnt=0,lim=(1<<m)-1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sum[0]=INT_MAX;
    for(int i=1;i<=lim;i++) sum[i]=sum[i-(i&-i)]&b[__builtin_ctz(i)+1];
    for(int i=1;i<=n;i++){
        static int dp[15];
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=lim;j++) dp[__builtin_popcount(j)]=max(dp[__builtin_popcount(j)],a[i]-(a[i]&sum[j]));
        for(int j=m;j>=1;j--) dp[j]-=dp[j-1],w[++cnt]=dp[j];
    }
    nth_element(w+1,w+k,w+cnt+1,greater<int>());
    cout<<accumulate(a+1,a+n+1,0ll)-accumulate(w+1,w+k+1,0ll)<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}