Convex Hull Optimization
Convex Hull Optimization이란, Convex Hull Trick이라고도 알려져있으며 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. IOI2002에 처음 나왔다고는 하나, 제대로 알려지기 시작한 것은 APIO2010 특공대 문제 이후라고 생각한다. 때문에 APIO2010 특공대 문제를 예시로 Convex Hull Optimization 설명을 시작하겠다. $S_i = \sum_{k=1}^{i} x_k$ 를 정의하자. 단, $S_0 = 0$ DP 배열을 아래와 같이 정의한다. $D_i$ = 1번부터 $i$번 병사까지 특공대를 나눌 때 전투력 합의 최대값. 단, $D_0 = 0$ 이 때, 점화식은 아래와 같이 된다. $D_i = \max(D[j] + A(S_i-S_j)^2 ..
공부
2016. 8. 23. 19:05
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Tree
- IOI2011
- IOI2014
- Knuth Optimization
- majority
- optimization
- Greedy Method
- idea
- Divide & Conquer
- Boyer-Moore Majority Vote Algorithm
- Dijkstra
- Boyer
- IOI2013
- vote
- TRIE
- Algorithm
- BOI
- IOI2012
- Dynamic Pramming
- Segment tree
- BOI 2009
- dynamic programming
- Splay Tree
- Parametric Search
- moore
- HackerRank
- BOI 2001
- ioi
- USACO
- z-trening
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
글 보관함