题解：P10242 [THUSC 2021] Emiya 家明天的饭

· · 题解

思路

我们显然有一个 O(m2^n) 的暴力，枚举哪些人未离席的集合 S，然后设喜欢第 i 个菜的人构成集合 s_i，若 S\subseteq s_i，则这道菜可以制作。设 f_{i,S} 为在未离席的人构成的集合的子集包含 S 时第 i 个人的总贡献。则答案为：

\max_S\sum_{i\in S} f_{i,S}

其中 f_{i,S} 为：

\sum_{S\subseteq s_j} a_{i,j}

不难发现其实 f_{i,S} 的求法相当劣，需要优化。可以让 f_{i,S} 初始为在未离席的人构成的集合为 S 时第 i 个人的总贡献。然后，枚举 f_{i,S} 所有的超集，加入 f_{i,S} 即可。使用枚举集合与子集的方法，这一步可以做到 O(3^n)。我们的总时间复杂度也被优化到了 O(n3^n+nm+2^n)，也就是 O(n3^n)。

这样仍然是超时的，但如果你学习过 SOS DP 就可以做到在 O(n2^n) 的时间内做到将一个集合加上其所有的超集。SOS DP 是使用二进制优化来优化枚举超集的操作，可以自行学习。最后总复杂度 O(n^22^n)，可以通过此题。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, ans;
int a[25][2000005], dp[25][2000005];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)cin >> a[i][j];
    }
    for (int i = 1; i <= m; i++) {
        int now = 0;
        for (int j = 1; j <= n; j++) {
            if (a[j][i] != -1)now |= 1 << (j - 1);
        }
        for (int j = 1; j <= n; j++) {
            if (a[j][i] != -1)dp[j][now] += a[j][i];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k <= (1 << n) - 1; k++) {
                if (!(k & (1 << (j - 1))))dp[i][k] += dp[i][k | (1 << (j - 1))];
            }
        }
    }
    for (int i = 0; i <= (1 << n) - 1; i++) {
        int now = 0;
        for (int j = 1; j <= n; j++) {
            if (i & (1 << (j - 1)))now += dp[j][i];
        }
        ans = max(ans, now);
    }
    cout << ans;
    return 0;
}