自动搬运

查看原文

来自洛谷，原作者为

	inc1ude_c 兴尽悲来，喜多郁代

搬运于2025-08-24 22:56:06，当前版本为作者最后更新于2024-05-02 09:51:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先发现人很少，所以我们考虑菜对人而不是人对菜。设一个菜喜欢一个人当且仅当这个人喜欢这个菜。

设 $p_i$ 为第 $i$ 道菜喜欢的人的集合。

答案即为：

$S$ 是最后必须留下来的人的集合，然后考虑留下来的人会遇到哪些菜，其菜所喜欢的人必须是留下来的人的超集（不然就会有人被气走）。

设 $f_{i,s}=\sum\limits_{p_j=s}a_{i,j}$。

答案为：

发现 $\sum_{S\subseteq T}f_{i,T}$ 就是且运算的 FWT。然后就做完了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int N=22,NN=(1<<N)+10,M=1e6+10;
int n,m;
int a[N][M],p[M];
ll f[N][NN];
void FWT(ll *f,int len){
    for(int mid=1;mid<len;mid<<=1){
        for(int i=0;i<len;i+=(mid<<1)){
            for(int j=0;j<mid;j++){
                f[i+j]+=f[i+j+mid];
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        rep(j,1,m){
            scanf("%d",&a[i][j]);
            if(a[i][j]!=-1)p[j]|=(1<<(i-1));
        }
    }
    rep(i,1,n){
        rep(j,1,m){
            f[i][p[j]]+=a[i][j];
        }
        FWT(f[i],1<<n);
    }
    ll ans=0;
    rep(s,0,(1<<n)-1){
        ll tans=0;
        rep(i,1,n){
            if(!(s&(1<<(i-1))))continue;
            tans+=f[i][s];
        }
        ans=max(ans,tans);
    }
    printf("%lld",ans);
    return 0;
}