백준 3056 - 007 [Python]

https://www.acmicpc.net/problem/3056

3056번: 007

DP Using Bitfield

 

dp[bit] = (상태 bit에서의 최대 확률) 이라고 정의하자.

dp[bit] = max(dp[bit], f(x + 1, bit | (1 << i)) * a[x][i] / 100) 이 된다.

 

템플릿 코드

import sys, math
import heapq
 
from collections import deque
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
#input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
#gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
#prime
def isPrime(x):
    if x<=1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True
 
# Union Find
# p = {i:i for i in range(1, n+1)}
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
def getPow(a, x):
    ret = 1
    while x:
        if x&1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x>>=1
    return ret
 
def getInv(x):
    return getPow(x, MOD-2)

 

dp = [-1 for _ in range(1 << 20)]
def f(x, bit):
    if x == n:
        return 1
    if dp[bit] != -1:
        return dp[bit]
    for i in range(n):
        if not bit & (1 << i):
            dp[bit] = max(dp[bit], f(x + 1, bit | (1 << i)) * a[x][i] / 100)
    return dp[bit]
 
n = ip()
a = [lmip() for _ in range(n)]
print(f(0, 0) * 100)