题目链接
解析
由于人数 \(n\) 很小，考虑对人数进行状压。拆贡献，设 \(f_{i,S}\) 表示满足集合 \(S\) 内所有朋友的要求时，第 \(i\) 位朋友对结果做的贡献。那么所有朋友做的贡献加起来的结果 \(\sum_{i\in S} f_{i,S}\) 即为朋友集合为 \(S\) 时的结果，所有集合结果取最大值即为答案。
考虑怎么求 \(f\)。设 \(T_j\) 表示喜欢第 \(j\) 道菜的朋友集合，那么第 \(j\) 道菜满足集合 \(S\) 内所有朋友的要求当且仅当 \(S\subseteq T_j\)。于是，对于 \(f_{i,S}\)，我们有：
\[f_{i,S} = \sum_{S \subseteq T_j} a_{i,j}
\]
相当于对每个 \(i\) 都做一遍 SOSDP。时间复杂度 \(O(n^2 2^n)\)。
代码
/*
*/
#include <bits/stdc++.h>
#define eps 0.0000000001
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
//#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef unsigned ui;
typedef pair<int,int> pii;
const int N = (1 << 20) + 5,M = 20 + 5,P = 2000000,mod = 1e9 + 7,mod2 = 1e9 + 7,b1 = 131,b2 = 13331;
ll f[M][N],a[M][N],t[N];
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j] >= 0){t[j] |= (1 << (i - 1));}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(t[j] & (1 << (i - 1))){f[i][t[j]] += a[i][j];} }}for(int i=1;i<=n;i++){for(int j=0;j<(1 << n);j++){if(!(j & (1 << (i - 1)))){for(int k=1;k<=n;k++)if(j & (1 << (k - 1))){f[k][j] += f[k][j ^ (1 << (i - 1))];}}}}ll res = 0;for(int i=0;i<(1 << n);i++){ll x = 0;for(int j=1;j<=n;j++){x += f[j][i];}res = max(x,res);}cout<<res;return 0;
}