The elimination rule—removing consecutive identical elements when their count reaches a threshold $k$—suggests an interval dynamic programming approach. A two-dimensional DP state is insufficient because it cannot capture how the leftmost element in a segment is eventually removed. To resolve this, we introduce a third dimension that tracks how many additional balls matching the left endpoint have been virtually prepended to the current interval.

Let dp[l][r][p] denote the minimum number of operations needed to completely eliminate the subarray from index $l$ to $r$, assuming there are already $p$ extra balls of value a[l] attached just before position $l$.

Two main strategies govern the transitions:

1. Direct elimination of the leftmost group: If adding $p$ virtual balls to the existing a[l] results in exactly $k$ identical balls (i.e., $p + 1 = k$), then the entire group can vanish in one move. This yields:

   if (p == k - 1)
       dp[l][r][p] = min(dp[l][r][p], dp[l + 1][r][0]);
   else
       dp[l][r][p] = min(dp[l][r][p], dp[l][r][p + 1] + 1);
   

   The second case accounts for inserting one more matching ball to progress toward elimination.

2. Merging with a matching element inside the interval: If some position $x \in [l+1, r]$ satisfies a[x] == a[l], we may first eliminate the segment $(l, x)$, then merge a[l] with a[x]. After clearing [l+1, x-1], the remaining structure combines the prepended $p+1$ copies of a[l] with the suffix starting at $x$:

   if (a[l] == a[x])
       dp[l][r][p] = min(dp[l][r][p], dp[l + 1][x - 1][0] + dp[x][r][min(p + 1, k - 1)]);
   

   When $x = l+1$, the middle segment is empty, simplifying to:

   if (a[l] == a[l + 1])
       dp[l][r][p] = min(dp[l][r][p], dp[l + 1][r][min(p + 1, k - 1)]);
   

Initialization sets dp[i][i][p] = k - p - 1 for all valid $p$, representing the cost to eliminate a single ball given $p$ prepended matches.

The final answer is dp[1][n][0], indicating the minimal operations to clear the full array with no prepended balls.

#include <bits/stdc++.h>
using namespace std;

const int N = 105, INF = 0x3f3f3f3f;
int n, k, a[N], dp[N][N][7];

int main() {
    cin >> n >> k;
    memset(dp, INF, sizeof(dp));
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i)
        for (int p = 0; p < k; ++p)
            dp[i][i][p] = k - p - 1;

    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            for (int p = k - 1; p >= 0; --p) {
                if (p == k - 1)
                    dp[l][r][p] = min(dp[l][r][p], dp[l + 1][r][0]);
                else
                    dp[l][r][p] = min(dp[l][r][p], dp[l][r][p + 1] + 1);

                if (a[l] == a[l + 1])
                    dp[l][r][p] = min(dp[l][r][p], dp[l + 1][r][min(p + 1, k - 1)]);

                for (int x = l + 2; x <= r; ++x)
                    if (a[l] == a[x])
                        dp[l][r][p] = min(dp[l][r][p], dp[l + 1][x - 1][0] + dp[x][r][min(p + 1, k - 1)]);
            }
        }
    }

    cout << dp[1][n][0] << endl;
    return 0;
}