문제 가장 먼저 문제에서 다음을 관찰해야 한다 :어떤 수열이 최종적으로 k개의 그룹으로 나누고, 이 각 그룹의 합이 인덱스 순서대로 $s_1,s_2,\cdots,s_k$ 라고 하자.그러면 처음 수열에서 어떠한 순서로 나누든간에 점수는 $\sum_{1 \leqslant i 즉, 우리는 이제 어떤 수열을 적절하게 m번 나누기만 하면 된다. (위의 관찰 이전에는 그룹을 나누는 순서도 고려했어야 되지만, 이제는 순서는 고려할 필요가 없게 되었다.) $\text{dp}[k][i]$를 "수열의 1~i 까지의 구간에 대해서 k번 나눌때 얻을 수 있는 최대 점수"로 정의하고 점화식을 구해보자.$$\begin{align}\text{dp}[k][i]&= \max_{1 \leqslant k &= \max_{1 \leqsla..

문제 먼저 사탕의 개수를 최대화 하는 문제는 $k$번째 사탕을 $t_k$시간에 먹었다고 할때 $t_k$ 합을 최소화 하는 문제와 동치라는것을 알 수 있다. (문제를 좀더 쉽게 하기 위해 일단 $t_k \leqslant m$이라는 가정을 하자.) 그리고 나서 가장 먼저 $\text{dp}[l][r]$을 사탕의 구간 $l \sim r$ 에 대해서 $t_k$합의 최솟값으로 정의하려고 시도해 볼 수 있다. 하지만 이렇게 하면 적절한 점화식을 구할 수 없다. $k$번째로 먹은 사탕을 시간 $t_k$때 먹었다고 하자. ($t_k$의 정의가 이전과 다음에 주의하자.)우리는 최소화 하려는 대상은 $t_1 + t_2 + \cdots + t_n$ 이다. 그런데 잘 생각해보면 $t_2,t_3,\cdots,t_n$에는 모두 ..

문제 먼저 $w_i \geqslant w_j, h_i \geqslant h_j$ 인 모든 $(i,j)$ 쌍에 대해서 $j$번 직사각형을 제거할 수 있다.이를 통해 $i 그러면 $O(N^2)$ dp로 문제를 풀 수 있다.$\text{dp}[i]$ : 1~i 까지의 직사각형들만 사용해서 문제를 풀 때의 최소 비용$\text{dp}[0] = 0$$\text{dp}[i] = \min_{0 \leqslant j  이제 CHT를 이용해서 $O(N)$ 으로 문제를 풀면 된다.