题目链接
题解
\(f[i][j][k]\)表示在消除了\((i,j)\)，在后面加上了\(k\)个珠子的总的珠子数。
考虑三种决策：（题目给出的\(k\)在下文表示成\(K\)）
决策1
当\(k<K-1\)时，可以考虑在加一个珠子，也就是状态\(f[i][j][k+1]\)转移得到\(f[i][j][k]\)。因为加上了一个珠子，那么就方程为\(f[i][j][k]=min(f[i][j][k+1]+1)\)
决策2
如果\(k=K+1\)，说明这个可以消除，也就是从\(f[i][j][k]=f[i+1][j][0]\)。
决策3
如果\(i\)的颜色和\(i+1\)的颜色相同，那么可以把\(i\)加入到\(i+1\)中，那么方程就是\(f[i][j][k]=f[i+1][j][k+1]\)。
答案显然就是\(f[1][n][0]\)。
鉴于这一道题目方程和方程之间状态的转移比较零散，所以用记忆化搜索实现比较简单。
代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 105
using namespace std;
int f[N][N][N], a[N];
int n, K;
int DP(int l, int r, int k) {
if (f[l][r][k] != -1) return f[l][r][k];
if (l > r) return 0;
f[l][r][k] = inf;
if (k < K - 1) f[l][r][k] = min(f[l][r][k], DP(l, r, k + 1) + 1);
if (k == K - 1) f[l][r][k] = DP(l + 1, r, 0);
for (int i = l + 1; i <= r; i ++)
if (a[i] == a[l]) f[l][r][k] = min(f[l][r][k], DP(l + 1, i - 1, 0) + DP(i, r, min(K - 1, k + 1)));
return f[l][r][k];
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> K;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(f, -1, sizeof(f));
DP(1, n, 0);
cout<< f[1][n][0] << endl;
return 0;
}