[BOJ] 4008번: 특공대

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

$O(N^2)$ 식은 쉽게 착안할 수 있습니다.

$D_i = i$번째 병사까지 배치했을 때 최댓값이라고 할 때, $D_i = \max_{j < i} D_j + Attack_power_of (j+1 to i)$입니다. 이제 식을 적절하게 바꿔 Convex Hull Trick을 사용할 수 있는 형태로 바꾸면 됩니다. 수식을 다 옮겨적긴 조금 귀찮네요ㅎㅎ..

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