LeetCode 1349. Maximum Students Taking Exam

(题目链接)https://leetcode.com/problems/maximum-students-taking-exam/

题意:

让你给学生安排座位,有’#’号的不能坐,每个学生能看到左右和左上右上四个方向的人的试卷,请你给学生们安排座位使得学生人数最多

思路

经典的状态压缩dp问题,观察到n和m最大只有8,很明显可以利用二进制来确定第一行的状态,只要第一行定了剩下几行也就定的,最后维护最一行的最大值即可。
$dp[i][j]$表示第$i$为第$j$个状态时的最大值,状态转移方程如下:
$dp[i][j] = max(dp[i][j], dp[i-1][k] + num-of-one[j])$

需要注意的是要提前处理好每一行不能坐的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def CountBinary(self, num):
_ = 0
while num:
if num & 1:
_ += 1
num = num >> 1
return _
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0])
mp = [0]*m
for i in range(m):
for j in range(n):
if seats[i][j] == '#':
mp[i] += (1 << j)
num = []
sta = []
for i in range(2**n):
if not ((i & (i << 1)) and (i & (i >> 1))):
num.append(self.CountBinary(i))
sta.append(i)
dp = [[0]*(2**n) for i in range(m)]
for i in range(len(num)):
if not (sta[i] & mp[0]):
dp[0][sta[i]] = num[i]
for i in range(1, m):
for j in range(len(num)):
if sta[j] & mp[i]:
continue
#if sta[j] & (sta[j] >> 1) and sta[j] & (sta[j] << 1):
# continue
for k in range(len(num)):
if sta[k] & mp[i - 1]:
continue
if (sta[j] & (sta[k] >> 1)) or (sta[j] & (sta[k] << 1)):
continue
dp[i][sta[j]] = max(dp[i][sta[j]], dp[i - 1][sta[k]] + num[j])
return max(dp[-1])


-------------本文结束感谢您的阅读-------------


本文标题:LeetCode 1349. Maximum Students Taking Exam

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2020年02月17日 - 16:02

最后更新:2020年02月17日 - 16:02

原始链接:https://statusrank.xyz/articles/5de19761.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!