APIO 14 Prob 2. 수열

ojuz 링크
Baekjoon Online Judge 링크

먼저 해야 할 observation은, 최종적인 점수에 관한 것이다.
쪼개진 \(k+1\)개의 부분의 각각의 합을 \(s_{1}, s_{2}, \cdots , s_{k+1}\)이라고 할 때, 점수는 \( \large \displaystyle{\sum_{1 \leq i<j \leq (k+1) }} s_{i} s_{j} \)이다.
증명은 간단하다. 임의의 두 원소가 다른 그룹에 속할 때, 그 둘이 서로 다른 그룹으로 쪼개지는 순간이 있고, 그 순간의 곱에는 그 두 원소의 곱이 포함되어있다.

이 식을 조금 더 정리해보자.

$$ \begin{align} \sum_{1 \leq i<j \leq (k+1)} s_{i} s_{j} &= \frac {\displaystyle{\sum_{i=1}^{k+1}} \displaystyle{\sum_{j=1}^{k+1}} (s_{i} s_{j}) - \sum_{t=1}^{k+1} {(s_{t})}^{2} }{2}\\ &= \frac {(\sum s_{i})^{2} - \sum (s_{i})^{2}}{2} \end{align} $$

마지막에 간단한 식이 나왔다. (분자는 항상 짝수임은 자명하다!)
앞의 항은 전체 원소의 합의 제곱과 같기 때문에, 점수를 최대화하기 위해서는 뒤의 항을 최소화시켜야 한다.

뒤의 항은 DP로 최소화시킬 수 있을 것 같지 않은가?!
prefix sum 배열 \(S_{i}\)를 잡자.
\( dp[0][0]=0, dp[0][i]=\infty \\
\begin{align} dp[t][i] &= \min_{0 \leq j < i} (dp[t-1][j] + (S_{i}-S_{j})^{2}) =  \min_{0 \leq j < i} (dp[t-1][j] + (S_{i})^{2}-2S_{i}S_{j}+(S_{j})^{2}) \\
&= S_{i}^{2} + \min_{0 \leq j < i} (-2S_{i}S_{j}+(dp[t-1][j]+(S_{j})^{2})) \end{align} \)

min함수 부분은 \(S_{i}\)에 대한 일차식이고, 그 계수 또한 \(j\)에 의해 결정된다.

따라서 모든 \(t\)에 대해서 convex hull trick을 적용할 수 있다.
시간복잡도는 \(O(NK)\) 혹은 \(O(NlgN \cdot K)\)이다. (convex hull trick의 구현에 따라 달라진다.)