트리 DP와 비트마스크 DP 문제 풀이
P1352 상사 없는 파티
트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다.
상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값
점화식:
val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가)
val[node][0] = Σ max(val[child][0], ...
7월 3일 21:12에 게시됨