문제무한한 격자판이 있다고 하자.각 셀은 0 또는 1의 상태를 가질 수 있다.각 셀은 단위 시간 마다 다음 규칙에 따라서 상태가 바뀐다.$t$ 시간에 어떤 셀의 위치를 $(r,c)$ 라고 할 때 $(r+1,c)$와 $(r,c+1)$ 위치의 셀이 모두 $1$ 이면 $t+1$시간에 $(r,c)$ 셀의 상태는 1이다.$t$ 시간에 어떤 셀의 위치를 $(r,c)$ 라고 할 때 $(r+1,c)$ 또는 $(r,c+1)$ 위치의 셀이 $0$ 이면 $t+1$시간에 $(r,c)$ 셀의 상태는 0이다.초기에 상태가 1인 셀들이 유한하다고 할 때, 시간이 충분히 흐른다면 모든 셀들의 상태가 0이 됨을 보이시오.증명$t$ 시간에 1인 셀의 개수를 $n_t$, 초기에 1인 셀의 개수를 $m=n_0$, 각 셀의 상태를 $s(r,..

문제 가장 먼저 문제에서 다음을 관찰해야 한다 :어떤 수열이 최종적으로 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$에는 모두 ..