[BOJ] 13263번: 나무 자르기

https://www.acmicpc.net/problem/13263

D[i]를 i번 전기톱을 사용할 수 있기 위해 필요한 충전 비용의 최솟값이라고 하면, b_n = 0이므로 N번 전기톱만 사용할 수 있게 되면 다른 모든 나무를 제거할 수 있고, 즉 우리는 D[N]이 정답임을 알 수 있습니다.

D_k = (j = 1 to k-1) min(a_k*b_j + D_j)이라는 식을 얻을 수 있고, 이를 O(N^2)으로 해결하는 대신 Convex Hull Trick을 이용해 O(N)에 해결할 수 있습니다. 맨 처음에는 실수연산을 회피하려 했으나 long long 범위를 초과해 어쩔 수 없이 double을 사용했습니다.

https://github.com/blisstoner/BOJ/blob/master/13263.cpp