Wednesday, July 30, 2014

Dynamic Programming Optimizations

Codeforces Blog Article of dynamic programming optimization techniques


Codeforces Round #189 (Div. 1) Problem C 는 전형적인 컨벡스헐 트릭 문제이다. APIO 2010 Commando 문제를 짠 지 몇 주 밖에 안 지났는데, 자꾸 코딩 실수하고 처음에 데크로 접근해버렸음ㅠㅠ... 몹쓸 습관이 생겨버린 거 같다. 자꾸 연습해서 빨리빨리 짤 수 있도록 해야겠다.
정리해보면, d[i] = min(d[j]+a[i](=x)*b[j])라는 점화식이 얻어진다. d[i]값은, 선분이 들어있는 리스트 중에서 현재 x값(a[i])이 다음 선분의 유효범위 최소 x값보다 크다면 계속 다음 선분을 보는 것을 반복하다가 더 이상 안될 때, 그 선분에 a[i]를 대입해서 구한다.
선분의 기울기는 단조 감소하는데, 매 i번째마다 선분을 삽입한다. 삽입할 때, Stack에 남아있는 선분(L) 중 top()의 것과 교점을 구해서, L의 유효범위 최소 x값보다 더 작거나 같다면 pop()하는 것을 반복. 결론적으로 O(N)
내 소스코드

컨벡스헐 트릭 문제 하나 더 풀고 오늘 공부는 정리해야겠다.
내일은 Knuth Optimization에 대해서 공부해봐야지.

No comments:

Post a Comment