DP19 cf 551 div2 D - Serval and Rooted Tree (tree, dp, 발상) https://codeforces.com/contest/1153/problem/D 문제를 재정의하는 방법이 새로워서 리뷰 루트가 1인 트리가 주어진다. 리프노드가 k개 있다면 각 리프노드에 1~k의 순열을 저장할 수 있다. 각 노드마다 min또는 max 성질이 주어지는데, 자식노드의 값중 최소 또는 최대를 값으로 갖는다는 의미다. 리프노드에 적절한 값을 넣어 루트에 저장될 수 있는 값 중 최대를 구하라. 현재 정점 u가 max 성질이 있다면, 그냥 자식 정점 값중 최대를 갖으면 된다. 문제가되는건 min성질이다. 예를들어서 min성질을 갖는 정점 u가 리프노드 3개를 자식으로 둔다면, 가장 작은 하나를 제외하고 2개의 숫자를 잃는다고 생각할 수 있다.(잘 생각해보면 u의 자식이 리프노드가 아니더라도 일반.. 2020. 3. 25. Codeforces #627 div3 F - Maximum white subtree (graph dp, reroot) https://codeforces.com/contest/1324/problem/F reroot 첫 성공 무방향트리가 주어진다. 각 정점마다 하얀색(1)또는 검은색(0)으로 색칠되어 있다. i번 정점을 포함하는 서브트리 중 하얀색정점의 개수 - 검은색 정점의 개수가 최대인 경우 그 값을 각각 구해라 (i=1,2,3,4...n) 1번 정점을 root로 하는 전체 트리에서 dp[u] : u를 포함한 서브트리에서 cntw-cntb 최대값 u에 인접한 v에 대해 ans[v] = dp[v] + max(dp[u],0)이다. v에서원하는 값 ans[v]가 u,v에대한 상태로만 정의되므로 reroot 적용가능하다. dp[u] -= max(dp[v],0) dp[v] += max(dp[u],0) go(u,v) dp[u] =.. 2020. 3. 14. BOJ 11982 - Angry cow (그리디, 전처리dp, 투포인터) https://www.acmicpc.net/problem/11982 어렵다 공식홈페이지와 rdd6584님의 코드를 보며 공부했습니다. 일직선위에 최대 5e4개의 표적이 n개 주어진다. 폭발반경이 R인 폭탄을 일직선 위에 던지려고 한다. 표적은 터지면 이전 폭발반경보다 1 작은 만큼의 폭발반경을 가지며 연쇄폭발한다. 적절한 곳에 폭탄을 던진다면 모든 표적을 부수기 위해 필요한 폭탄의 최소 폭발반경은 몇일까? 소수점 첫 자리까지 나타내라 폭탄은 어떤 두 표적 정 가운데에 떨어지는 것이 최적이다. ->(x+y)/2로 표적의 위치를 특정할 것이므로 표적의 위치는 xxx.5 혹은 xxx.0이다. 모든 표적의 좌표를 두배로 하고 폭발반경이 2씩 줄어든다고 처리하면 정수연산만으로 풀 수 있다. 표적은 오름차순 정렬해.. 2020. 2. 27. BOJ 1967 - 트리의 지름 https://www.acmicpc.net/problem/1967 제목이 곧 내용인 문제 트리의 지름을 구하라 https://suuntree.tistory.com/171아이디어에 대한 추가설명 임의의 점에서 제일 먼 점 u와 u에서 제일 먼 점 v사이의 길이를 구하면 된다. 어떤 점에서 제일 긴 곳까지의 길이는 어떻게 구할까? 가중치가 없는 트리에선 dfs의 깊이가 곧 길이가 된다. 이 문제는 가중치가 있는 그래프이므로 1대신 w 더해주면 된다. 모든 정점에서 이 길이의 최대를 찾으면 된다. dfs 깊이를 효과적으로 유지하려면 함수에 깊이를 의미하는 파라미터를 추가해주면 된다. dfs(u, prv, d)꼴로 한 번의 dfs로 가장 먼 점과 그때의 거리를 구할 수 있다. int n, dst, st; vec.. 2020. 2. 8. 이전 1 2 3 4 5 다음
