블로그 옮겼습니다
문제 링크 노드의 수가 100개 이하인 두개의 트리 g1, g2 가 주어진다. 두 트리의 루트 노드는 모두 1번 노드이다. 두 트리의 최대 공통 노드 수를 출력하는 문제이다. 쉽게 말해서 각 노드에 대해서 자식 노드들의 순서를 요리 조리 바꿔도 여전히 같은 트리이기 때문에 각 노드의 자식들의 순서를 요리 조리 바꿨을 때 두 트리중 모양이 일치하는 가장 노드가 많은 부분 트리의 노드 수를 구하는 문제이다. dp[a][b] : 트리 g1에서 노드 a를 루트로 하는 서브트리와, 트리 g2에서 노드 b를 루트로 하는 서브트리의 최대 공통 노드 수 라고 부분 문제를 정의하면 트리 dp 로 해결할 수가 있다. 그렇다면 부분 문제 테이블의 하나의 셀을 어떻게 채울까? 답은 MCMF 이다. dp[a][b] 에서 a의 ..
문제 링크 n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).수직선에 1, 2, ..., n 의 장소가 있다. m 개의 폭죽이 임의의 시간과 장소에서 발사된다.주인공은 1초에 d만큼 이동할 수 있다. 시작 위치는 아무데서나 시작해도 된다.i번 폭죽이 발사될 때 주인공이 x 지점에 있을 때 얻게되는 행복은 \(b_i - |a_i - x|\) 이다.이 때 모든 폭죽이 발사되고 난 후에 주인공이 얻은 행복의 양이 최대가 되도록 하고싶다.그 아랫줄부터는 m개의 폭죽의 대한 정보 ai, bi, ti 가 주어진다.ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109) dp[i][j] : t_i 시간에 j 위치에 있을 때 최대 행복도\(dp[..