ZUMA – Minimum Insertions to Eliminate Marbles

This problem is inspired by the COCI 2010 problem "ZUMA". Mirko arranges N marbles in a row, numbered from 1 to N, where the i-th marble has color c_i. He discovered that if he touches a contiguous segment of marbles of the same color and the length of the segment is at least K, then magic makes these marbles vanish. After that, the marbles that were to the left and right of the segment become adjacent.

Mirko has an unlimited supply of marbles. He wants to insert as few additional marbles as possible (in between the given marbles, or before the first marble or after the last marble) so that the entire sequence (the original N marbles plus the inserted ones) eventually vanishes by repeated applications of the magic.

Note:

Let \( dp(l,r,k) \) be the minimum number of insertions required to completely eliminate the marbles in the interval \( [l,r] \) given that there are \( k \) extra marbles to the right (adjacent to position \( r \)) that have the same color as the marble at position \( r \). The following transitions are used:

• Base Case: For a single marble (i.e. when \( l=r \)), \[ dp(l,l,k)=\begin{cases}0,&\text{if } k+1\ge K,\\ K-(k+1),&\text{otherwise.} \end{cases} \]
• General Case: For \( l<r \), one option is to remove the last marble alone: \[ dp(l,r,k)= dp(l,r-1,0)+ \begin{cases}0,&\text{if } k+1\ge K,\\ K-(k+1),&\text{otherwise.} \end{cases} \] Another possibility is to merge the marble at \( r \) with an earlier marble of the same color at index \( i \) (where \( l\le i<r \) and \( c_i=c_r \)): \[ dp(l,r,k)= \min_{l\le i < r \; \text{and} \; c_i=c_r} \{ dp(l,i,k+1)+dp(i+1,r-1,0) \}. \]

Your task is to compute the minimum number of inserted marbles needed to eventually remove the entire sequence.

inputFormat

The input consists of two lines:

• The first line contains two integers N and K where N (1 ≤ N ≤ 100) is the number of marbles, and K (2 ≤ K ≤ 10) is the minimum number of consecutive marbles of the same color needed to vanish.
• The second line contains N integers c₁, c₂, ..., c_N representing the colors of the marbles.

outputFormat

Output a single integer representing the minimum number of marbles you need to insert so that the entire sequence can vanish by repeatedly applying the magic described.

sample

3 3
1 1 1

0