中山专业外贸网站开发公司,部队网站模板,网站配色设计,秦皇岛建设网招聘文章目录1. 题目2. 解题1. 题目
有一份由 n 个问题组成的调查问卷#xff0c;每个问题的答案要么是 0#xff08;no#xff0c;否#xff09;#xff0c;要么是 1#xff08;yes#xff0c;是#xff09;。
这份调查问卷被分发给 m 名学生和 m 名导师#xff0c;学生…
文章目录1. 题目2. 解题1. 题目
有一份由 n 个问题组成的调查问卷每个问题的答案要么是 0no否要么是 1yes是。
这份调查问卷被分发给 m 名学生和 m 名导师学生和导师的编号都是从 0 到 m - 1 。
学生的答案用一个二维整数数组 students 表示其中 students[i] 是一个整数数组包含第 i 名学生对调查问卷给出的答案下标从 0 开始。
导师的答案用一个二维整数数组 mentors 表示其中 mentors[j] 是一个整数数组包含第 j 名导师对调查问卷给出的答案下标从 0 开始。
每个学生都会被分配给 一名 导师而每位导师也会分配到 一名 学生。 配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。
例如学生答案为[1, 0, 1] 而导师答案为 [0, 0, 1] 那么他们的兼容性评分为 2 因为只有第二个和第三个答案相同。 请你找出最优的学生与导师的配对方案以 最大程度上 提高 兼容性评分和 。
给你 students 和 mentors 返回可以得到的 最大兼容性评分和 。
示例 1
输入students [[1,1,0],[1,0,1],[0,0,1]], mentors [[1,0,0],[0,0,1],[1,1,0]]
输出8
解释按下述方式分配学生和导师
- 学生 0 分配给导师 2 兼容性评分为 3 。
- 学生 1 分配给导师 0 兼容性评分为 2 。
- 学生 2 分配给导师 1 兼容性评分为 3 。
最大兼容性评分和为 3 2 3 8 。示例 2
输入students [[0,0],[0,0],[0,0]], mentors [[1,1],[1,1],[1,1]]
输出0
解释任意学生与导师配对的兼容性评分都是 0 。提示
m students.length mentors.length
n students[i].length mentors[j].length
1 m, n 8
students[i][k] 为 0 或 1
mentors[j][k] 为 0 或 1来源力扣LeetCode 链接https://leetcode.cn/problems/maximum-compatibility-score-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[state] 老师被选择的情况是 state 的二进制位1 表示的状态时 的最大得分和
class Solution:def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) - int:n len(students)dp [0 for _ in range(1n)]def score(x, y):return sum([1 if (xi^yi)0 else 0 for xi, yi in zip(x, y)])# 预处理出来学生和老师的得分scores [[0 for i in range(n)] for i in range(n)]for i in range(n):for j in range(n):scores[i][j] score(students[i], mentors[j])# DPfor i in range(0, n): # 枚举学生样本for state in range(0, 1n): # 枚举老师的状态if bin(state).count(1) i: # 老师被选的个数应该为 i 个了for j in range(n):if state(1j) 0: # j 号 老师还没有被选dp[state|(1j)] max(dp[state] scores[i][j], dp[state|(1j)])return dp[-1]56 ms 14.9 MB Python3
上面是 state 是之前的状态
如果 state 是现在的状态则代码是
class Solution:def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) - int:n len(students)dp [0 for _ in range(1n)]def score(x, y):return sum([1 if (xi^yi)0 else 0 for xi, yi in zip(x, y)])# 预处理出来学生和老师的得分scores [[0 for i in range(n)] for i in range(n)]for i in range(n):for j in range(n):scores[i][j] score(students[i], mentors[j])# DPfor state in range(1, 1n): # 枚举老师的状态i bin(state).count(1) # 老师被选的个数 i 个, 当前学生下标是 i-1for j in range(n):if state(1j): # 学生 i-1 选择了 j 号 老师dp[state] max(dp[state^(1j)] scores[i-1][j], dp[state])return dp[-1]我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
