Untitled
unknown
python
a month ago
833 B
2
Indexable
Never
dp = [[-1, -1] for _ in range(n + 1)] # dp 배열을 -1로 초기화하여 방문 여부 확인 for a, b in links: tree[a].append(b) # 방향 그래프 생성 def dfs(node, pick): if dp[node][pick] != -1: return dp[node][pick] if pick: dp[node][1] = sales[node - 1] else: dp[node][0] = 0 cur_m = sys.maxsize for nxt in tree[node]: if pick: dp[node][1] += min(dfs(nxt, True), dfs(nxt, False)) else: dp[node][0] += min(dfs(nxt, True), dfs(nxt, False)) cur_m = min(cur_m, dfs(nxt, True) - dfs(nxt, False)) if not pick and cur_m < sys.maxsize: dp[node][0] += cur_m return dp[node][pick] res1 = dfs(1, False) res2 = dfs(1, True)
Leave a Comment