专栏文章

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

__ayaka_
P10242题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipnu28c
此快照首次捕获于
2025/12/03 15:03
3 个月前
此快照最后确认于
2025/12/03 15:03
3 个月前
查看原文

思路

我们显然有一个 O(m2n)O(m2^n) 的暴力，枚举哪些人未离席的集合 SS，然后设喜欢第 ii 个菜的人构成集合 sis_i，若 S⊆siS\subseteq s_i，则这道菜可以制作。设 fi,Sf_{i,S} 为在未离席的人构成的集合的子集包含 SS 时第 ii 个人的总贡献。则答案为：
max⁡S∑i∈Sfi,S\max_S\sum_{i\in S} f_{i,S}
其中 fi,Sf_{i,S} 为：
∑S⊆sjai,j\sum_{S\subseteq s_j} a_{i,j}
不难发现其实 fi,Sf_{i,S} 的求法相当劣，需要优化。可以让 fi,Sf_{i,S} 初始为在未离席的人构成的集合为 SS 时第 ii 个人的总贡献。然后，枚举 fi,Sf_{i,S} 所有的超集，加入 fi,Sf_{i,S} 即可。使用枚举集合与子集的方法，这一步可以做到 O(3n)O(3^n)。我们的总时间复杂度也被优化到了 O(n3n+nm+2n)O(n3^n+nm+2^n)，也就是 O(n3n)O(n3^n)。
这样仍然是超时的，但如果你学习过 SOS DP 就可以做到在 O(n2n)O(n2^n) 的时间内做到将一个集合加上其所有的超集。SOS DP 是使用二进制优化来优化枚举超集的操作，可以自行学习。最后总复杂度 O(n22n)O(n^22^n)，可以通过此题。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...