다른 블로그 포스팅을 보면서 공부한 것을 정리한 글입니다. Convex Hull Trick은 특정 형태의 점화식을 사용하는 다이나믹 프로그래밍을 빠르게 계산하기 위한 방법입니다.점화식은 다음과 같습니다.$$D_i = \min_{j 단, 여기서 Bj는 증가함에 따라 감소하는 값이어야 합니다. (aBb) Di의 최솟값을 구하기 위해 그래프의 개형을 구해봅시다.i가 같을 때는 Ai도 같은 값이니 x축을 Ai로 하여, y=Bj×x+Dj를 그리면 다음과 같습니다. j가 커질 수록 직선의 기울기 Bj는 감소합니다.y축과 만나는 점인 (0,Dj)는 증가할 수도 감소할 수도 있습니다. $D_i = \min_{j $= \min (D_..
