백준 4008 - 특공대 (C++)

문제 문제 링크 BOJ 4008 - 특공대 문제 요약 병사 $N$명의 전투력과 조정 전투력 등식 계수가 주어진다. 문제에 정의된 전투력 측정 방식을 따를 때, $n$명의 병사들에 대해 얻을 수 있는 최대 조정 전투력을 구해보자.

제한 TL : $1$ sec, ML : $64$ MB $1 ≤ N ≤ 1,000,000$ $-5 ≤ a ≤ -1$ $|b| ≤ 10,000,000$ $|c| ≤ 30,000,000$ $1 ≤ xi ≤ 100$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 CHT 대표 문제로 꼽히는 문제다. 물론 나도 CHT 태그를 타고 들어 왔지만 처음 내 반응은 "이게 왜 CHT?"

였다. 우선 연속 부분 수열 합을 고려해야 하므로 .....