사수아탕

summary:

수직선 상에 동일한 사탕 개수 $m$개로 이루어진 사탕 더미가 $n$개 있고 수아는 0에 있다.

사탕 더미에 도달하면 그 사탕 더미를 전부 먹을 수 있고, 1만큼 움직일때마다 현재까지 먹지 않은 모든 사탕 더미에 있는 사탕 개수가 1씩 감소한다.

수아가 먹을 수 있는 사탕의 최댓값을 구하는 문제이다.

solution:

먼저 사탕 더미를 좌표순으로 정렬하고, 앞에서 $x$번째 사탕의 위치를 $a_x$라고 하자.

맨 처음에 수아가 0에 있으므로, 이동 할 때마다 그때까지 먹지 않았던 사탕 더미에서 사탕 개수가 줄어든다.

사탕 더미에 도달한 시점에 줄어들어 있는 사탕의 개수를 페널티라고 하자.

그러면 만약 $k$개의 사탕 더미를 먹었다면 그때 먹은 사탕의 개수는 $k*m$ - 이때까지 먹은 모든 사탕더미의 페널티의 합 일 것이다.

그리고 다음과 같이 정의하면,

$L(i,j,k)$: $a_i,a_{i+1},\dots,a_j$가 전부 존재하지 않을 때(존재하지 않는다고 가정하므로 먹을 수도 없다), $a_i$에서 0초에 출발해 k개의 사탕을 추가로 먹을 때 드는 페널티(먹은 사탕 더미들에서 사탕이 줄어드는 개수)의 합의 최솟값

$R(i,j,k)$: $a_i,a_{i+1},\dots,a_j$가 전부 존재하지 않을 때, $a_j$에서 0초에 출발해 k개의 사탕을 추가로 먹을 때 드는 페널티의 합의 최솟값

$a_i,a_{i+1},\dots,a_j$를 이미 먹은 상태라고 가정하므로, $L(i,j,k)$의 상태가 되기 위해서는 맨 왼쪽 사탕더미($a_i$)가 가장 마지막으로 먹은 사탕일 것이고, $R(i,j,k)$의 상태는 $a_j$를 가장 마지막으로 먹은 상태일 것이다.

$L(i,j,k)$, $R(i,j,k)$의 상태에서 사탕더미 하나를 더 먹으려면 $a_{i-1}$과 $a_{j+1}$중 하나를 선택해서 먹어야 하고, 페널티는 각각 $a_i$는 $a_i-a_{i-1}$,$a_j-a_i$, $a_j$는 $a_{j+1}-a_j$, $a_j-a_{i-1}$이 되고, 그 다음 먹을 $k-1$개의 사탕 더미에도 역시 같은 페널티를 적용해야 한다.

따라서 점화식은 다음과 같다.

\[L(i,j,k)=min({L(i-1,j,k-1)+k*(a_i-a_{i-1},R(i-1,j,k-1)+k*(a_j-a_{i-1})})\] \[R(i,j,k)=min({L(i,j+1,k-1)+k*(a_{j+1}-a_i),R(i,j+1,k-1)+k*(a_{j+1}-a_j)})\]

$a_s$= 좌표가 0인 곳이라고 하고 그곳에는 사탕이 없다고 하면, 정답은

$max(k*m- L(s,s,k)) : 0 \le k \lt n) $가 된다.