D

summary:

1~$n$까지의 color를 가지고 있는 공이 랜덤하게 놓여 있다. 공들을 정렬하기 위해 아래 두 개의 operation을 쓸 수 있는데, 두 번째 operation의 최소 사용 횟수를 모든 $(1 \leq n)$에 대하여 구하는 문제이다.

1. k개의 0 color의 공을 삽입한다.
2. 0 color를 가지고 있는 공에 인접한 공을 배열의 원하는 곳으로 옮긴다.

solution:

배열 내에 어떠한 증가 수열중 하나를 $S$라고 하고, 그때 $S$에 속하지 않은 다른 원소의 segment 개수를 $f(s)$라고 하자.

예를 들어, $C={2,4,3,6,5,1,7}$ 에서 $S={2,3,5}$라고 하면 $[2,2],[4,4],[6,7]$(각각 {4},{6},{1,7})들이 $S$에 속하지 않은 segment이므로 $f(s)=3$이 된다.

$S$에 속하지 않은 공만 operation 2로 옮기려고 한다면, 각각의 segment에 0 color의 공이 최소 하나씩은 필요하므로 $f(s) \leq k$이어야 한다.

그리고 하나의 원소는 한번만 옮기면 되기 때문에 총 비용은 $n - \lvert S \rvert$이다.

정리하자면 $f(s) \leq k$인 모든 $S$에 대해 $n - \lvert S \rvert$의 최솟값을 구하면 되는 것이다.

dp를 이용해서 해결하는데,

$d_{i,j}$: $c_i$까지의 공만 사용해서 $f(s)$가 $j$가 되게 $S$를 선택했을 때 $\lvert S \rvert$의 최댓값으로 정의해서 $f(s) \leq k$에 맞게끔 최솟값을 구해서 해결해주면 된다.

$O(n^3)$이지만 숫자가 널널해서 괜찮다.

---

에디토리얼 이해가 안돼서 며칠동안 고민했는데, 에디토리얼을 모호하게 쓴건지 내가 이해를 못한건지 몰라도 정말 괴로웠다.