백준 - 수열 나누기(10067)

문제

 

가장 먼저 문제에서 다음을 관찰해야 한다 :

어떤 수열이 최종적으로 k개의 그룹으로 나누고, 이 각 그룹의 합이 인덱스 순서대로 $s_1,s_2,\cdots,s_k$ 라고 하자.

그러면 처음 수열에서 어떠한 순서로 나누든간에 점수는 $\sum_{1 \leqslant i < j \leqslant n} s_i \cdot s_j$ 로 동일하다.

즉, 우리는 이제 어떤 수열을 적절하게 m번 나누기만 하면 된다. (위의 관찰 이전에는 그룹을 나누는 순서도 고려했어야 되지만, 이제는 순서는 고려할 필요가 없게 되었다.)

 

$\text{dp}[k][i]$를 "수열의 1~i 까지의 구간에 대해서 k번 나눌때 얻을 수 있는 최대 점수"로 정의하고 점화식을 구해보자.

$$
\begin{align}
\text{dp}[k][i]
&= \max_{1 \leqslant k < i} \left[ \text{dp}[k-1][j] + s_j (s_i - s_j) \right] \\
&= \max_{1 \leqslant k < i} \left[ \text{dp}[k-1][j] - s_j^2 + s_j s_i \right]
\end{align}
$$

with $s_l = \sum_{i=1}^{l} a_i$, $\text{dp}[0][i] = 0 \forall 1 \leqslant i \leqslant n$

이 dp 점화식을 잘 보면 $\text{dp}[k-1][j] - s_j^2 + s_j s_i = (s_j)s_i + (\text{dp}[k-1][j] - s_j^2)$는 $s_i$에 대한 직선 이고 $s_i$가 단조 증가 하므로, CHT를 사용해서 내부 for 문을 $O(1)$만에 계산할 수 있다.

 

CHT를 이용하지 않은 알고리즘은 다음과 같다.

Algorithm 1 : not using CHT optimization

 

위의 알고리즘을 CHT로 구현할때, $\text{dp}[k][i]$를 계산할때는 $ \text{dp}[k-1][k], \text{dp}[k-1][k+1], \text{dp}[k-1][k+2], \cdots, \text{dp}[k-1][i-1] $ 에 대한 직선들만 이용해야된다는 부분을 주의해서 구현하자.