컨벡스 헐트릭

a가 감소할 때 dp[i] = min(dp[j] + a[j]b[i])꼴의 dp식을 n log n으로 풀기

dp[j] + a[j]b[i]를 ax + c (a=a[j], c=dp[j])꼴의 직선식으로 생각하여 푸는 것이다.

직선은 앞선 직선과의 교점과 기울기 절편을 데이터로 하여 저장한다. 첫번째 직선은 y축과의 교점으로 한다.

직선은 벡터에 저장한다. 새로운 직선을 추가할 때는 기존의 직선과 비교한다. 구간 내에서 최소값을 갖지 않는 직선은 삭제한다.

dp[i]는 이분탐색을 이용하여 찾을 수 있다.

b[i]를 교점에 대해 이분탐색 한다. 벡터에 들어가 있는 직선들의 교점은 정렬돼 있어서 가능하다.