구사과

(LCD Soundsystem, 2005)

https://www.acmicpc.net/problem/12010 이해가 안가면 이 글과 참고해서 보면 좋다 : http://usaco.org/current/data/sol_landscape_platinum_open16.html여담으로 이 문제는 KOI 2005 소방차와 상당히 유사한 문제다. 같이 보면 좋을 듯 하다. http://koistudy.net/?mid=prob_page&NO=313 1. O((NK)^2)dirt의 개수만큼 위치를 저장해 놓은 수열을 펴보자. 예를 들어 3, 1, 5, 1과 같이 수열이 주어지면 0, 0, 0, 1, 2, 2, 2, 2, 2, 3과 같은 형태로 수열을 바꾸는 것이다.수열 A, B가 있을 때 진행하는 연산에 대해서 다시 생각해 보면* 1. 추가 -> 수열 B에 ..

https://www.acmicpc.net/problem/3319한동안 글을 한꺼번에 썼었는데 나눠 쓰는 게 여러모로 나을 듯 하다. 앞으로 그런 방향으로 바꿔나가려고 함.언제봐도 신기한 harbingers 문제를 다시 리뷰하려고 한다. O(N^2)dp[i] = Min(dp[j] + (depth(i) - depth(j)) * V[i]) + S[i] for all j = (ancestor of i) 이다. Special Cases : Line O(NlgN) 일직선에서 이 문제는 아주 유명한 컨벡스 헐 트릭이다. (depth(j), func(j)) 라는 형태의 일차함수가 순서대로 들어오고, V[i] 쿼리를 이진 탐색으로 처리해 주면 된다. 이해가 안가면 여기서 멈추고, http://dyngina.tistor..