dynamic_programming 썸네일형 리스트형 BOJ 25392 - 사건의 지평선 (D3) 사용 알고리즘 Segment Tree + SCC + 위상정렬 dp 풀이 일단 어떻게 했는진 몰라도 i->L~R 간선을 잘 이어줬다고 치자. 무한 번 표시된다 = 사이클에서 돌고 있다는 의미이다. 따라서 사이클 내부에서 가장 큰 원소를 찾으면 그 사이클 내부에서의 정답이 된다. 단 어떤 사이클 u에서 v로 간선이 있는경우, u에서의 정답은 max(u 내부에서의 정답, v 내부에서의 정답)이다. 따라서 위상정렬 dp로 순차적으로 사이클에서의 최댓값을 결정해나가면 된다. 이제 i->L~R 간선을 깔끔하게 처리하는 법만 생각하면 된다. L~R은 구간이다. 구간 크기가 O(N)이므로 간선이 최대 O(N^2)개가 생긴다. 그렇다면 구간을 O(logN) 정도로 표현할 수 있다면 추가해야 하는 간선은 O(NlogN)개.. 더보기 이전 1 다음
