Codeforces Round #627) F. Maximum White Subtree ( C / C++)
1. 문제 링크 https://codeforces.com/contest/1324/problem/F Problem - F - Codeforces codeforces.com 2. 문제 개요 n개의 정점, n-1개의 간선을 가진 tree가 주어진다. 트리의 값이 0이면 black, 1이면 white이다. 3. 문제 힌트 DP top-down , bottom - up 2가지를 모두 써야 한다. dp[index]를 정의해야 하는데, dp[next] += max(dp[cur],0) 모두 연결된 간선에 대해서 max를 반복해야 할 것이다. 4. 문제 풀이 힌트의 의미를 문제의 흐름과 함께 풀어보자. 일단 dp의 초기값은 검은색이면 -1, 흰색이면 1로 두고 시작하자. 예제의 그림을 보면, 다음과 같다. 루트는 의미 ..
알고리즘/Dynamic Programming
2020. 4. 11. 00:27