Участник:Krivosheev.ah/maximum-students-taking-exam

Материал из DISCOPAL
< Участник:Krivosheev.ah
Версия от 15:03, 2 декабря 2020; Krivosheev.ah (обсуждение | вклад) (Новая страница: «Python3 https://leetcode.com/problems/maximum-students-taking-exam/ <code-python> class Solution: def maxStudents(self, seats: List[List[str]]) -> int:…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Python3

https://leetcode.com/problems/maximum-students-taking-exam/

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m = len(seats)
        n = len(seats[0])
        validity = [0]* m
        stateSize = 1<<n 
        dp = [[0 ]*stateSize for _ in range(m)]        
        ans = 0
        for i in range(m):
            for j in range(n):
                validity[i] = (validity[i] << 1) + (1 if seats[i][j] == '.' else 0)
        for i in range(m):
            for j in range(stateSize):
                dp[i][j] = -1
        for i in range(m):
            for j in range(stateSize):
                if (j & validity[i]) == j and (j & (j>> 1) == 0):
                    if i == 0: 
                        dp[i][j] = bin(j).count('1')
                    else:
                        for k in range(stateSize):
                            if (j & (k>>1)) == 0 and ((j >>1) & k) ==0 and dp[i-1][k] != -1:
                                dp[i][j] = max(dp[i-1][k]+bin(j).count('1'), dp[i][j])
                    ans = max(ans, dp[i][j])
        return ans