Open Wizmann opened 3 years ago
Problem
给你M种（M <= 50）互不相同的数，每个数有q[i]个。
现在有N（N <= 10）个人，每个人需要r[i]个相同的数。
问是否能满足所有人的要求。
小结论：只需要前N种数量最多的数即可。
将M种数从多到少排列。将N个人的需求全排列，进行匹配。
时间复杂度O(N! * N)
DFS搜索。时间复杂度同1类似，剪枝到位的话会快很多。
将M种数从多到少排列。将N个人的需求从多到少排列。
假设前K种数能满足N个人中某个子集B的需求。
我们向这个子集中加入一个人，形成了个新的集合B1 = B | (1 << t)。设B1的子集B1A ^ B1B = B1，我们可以判断B1集合的子集B1A是否能被前K - 1种数满足，然后将剩下的子集B1B被第K种数满足。
使用DP的方法即可求解。
题意
Problem
给你M种（M <= 50）互不相同的数，每个数有q[i]个。
现在有N（N <= 10）个人，每个人需要r[i]个相同的数。
问是否能满足所有人的要求。
解法
小结论：只需要前N种数量最多的数即可。
暴力解法1
将M种数从多到少排列。将N个人的需求全排列，进行匹配。
时间复杂度O(N! * N)
暴力解法2
DFS搜索。时间复杂度同1类似，剪枝到位的话会快很多。
正常解法
将M种数从多到少排列。将N个人的需求从多到少排列。
假设前K种数能满足N个人中某个子集B的需求。
我们向这个子集中加入一个人，形成了个新的集合B1 = B | (1 << t)。设B1的子集B1A ^ B1B = B1，我们可以判断B1集合的子集B1A是否能被前K - 1种数满足，然后将剩下的子集B1B被第K种数满足。
使用DP的方法即可求解。