mhy908의 PS 블로그 mhy908의 PS 블로그

https://www.acmicpc.net/problem/13138 13138번: Fairies' Sorcery 첫 번째 줄에는 요정의 수 N과 요정이 마법을 쓰는 횟수 M이 주어진다. (2 ≤ N, M ≤ 100,000) 두 번째 줄부터 M-1개의 줄에는 요정들의 마법이 주어진다. '2 P Q'는 P번 요정과 Q번 요정이 마법을 동시에 www.acmicpc.net 두 명의 요정이 마법을 사용하는 것은 상수시간에 처리가 가능하지만, 한명의 요정이 마법을 쓰는 것은 처리가 까다롭다. 파훼법은, 0번 요정을 임의로 추가하여 현재 있는 요정들을 0번을 기준으로 오른쪽으로 읽어온다고 가정하면 한명의 요정이 마법을 쓰는 것은 그 요정과 0번 요정의 위치를 swap하는 연산이 된다는 것이다. 이 순간에 마법을 써서..

정점이 N개인 트리가 주어질 때, 정점들을 적당히 지워 어떤 임의의 두 점 사이의 거리도 K를 넘지 않도록 하게 지우는 경우의 수를 세는 문제이다. N, K≤300000이다. #1. O(NK^2) Tree DP를 통해 세제곱 시간에 문제를 풀어낼 수가 있다. DP[u][a]를 u의 서브트리에 대해, 움직일 수 있는 정점의 최소 깊이가 a이도록 정점을 제거할 수 있는 경우의 수라 정의하자. 당연히 어떤 두 점 사이의 거리도 K를 넘으면 안된다는 조건을 만족하도록 제거하는 것이다. 편의상 모든 경로가 K이하인 것으로 조건을 바꾸고, 입력에서 주어진 K에 -1을 해주도록 하겠다. 이러한 조건 하에서 상태전이는 꽤 직관적이다. 어떤 임의의 정점에 대해 u의 자식 노드를 v1, v2라 하면, DP[u][max(a..

꽃들의 가격이 v[1], v[2], ..., v[N]까지 있을때, 이를 최대 K개의 구간으로 분할하여 각 구간에 대한 (구간에 있는 꽃의 개수)*(꽃들의 가격의 합)의 합을 최소화하라는 문제이다. 각 꽃은 정확히 하나의 구간에 포함되어야 하고, 임의의 1≤i