题目概述

有 $n$ 个珠子，可以把不少于 $K$ 个同样颜色的连续珠子消去并把两端接起来。现在可以随意加珠子，问最少加多少珠子使得所有珠子都消去。

解题报告

挺妙的DP：$f_{i,j,k}$ 表示在 $i$ 前加入 $k$ 个 $a_i$ 后把 $[i,j]$ 消去所需要的最少次数，那么有三种操作：

1. 加 $a_i$ ：$f_{i,j,k+1}+1\to f_{i,j,k}$ 。
2. 消去 $i$ ：$f_{i+1,j,0}\to f_{i,j,K-1}$ 。
3. 把后面颜色相同的接上来：$f_{i+1,t-1,0}+f_{t,j,k}\to f_{i,j,k+1}(a_i=a_t)​$ 。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=106;

int n,K,a[maxn],f[maxn][maxn][5];bool vis[maxn][maxn][5];

int DP(int L,int R,int x){
    if (L>R) return 0;if (L==R) return K-x-1;if (vis[L][R][x]) return f[L][R][x];
    vis[L][R][x]=1;int ans;if (x<K-1) ans=DP(L,R,x+1)+1; else ans=DP(L+1,R,0);
    for (int i=L+1;i<=R;i++) if (a[L]==a[i]) ans=min(ans,DP(L+1,i-1,0)+DP(i,R,min(K-1,x+1)));return f[L][R][x]=ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%d",&a[i]);return printf("%d",DP(1,n,0)),0;
}