4

Mirko 将 \(N\) 颗弹子排成一排，依次编号为\(1,2,\cdots,n\)。\(i\) 号弹子的颜色为\(c_i\) 。他发现，如果他触摸$ ≥K$ 颗连续的弹子，且这些弹子的颜色相同，魔法会使这些弹子消失；此后，这若干颗弹子前面的弹子便与这 若干 颗弹子后面的弹子相邻。

Mirko 家里有很多弹子，他想在这 \(N\)颗弹子之间（也可以在开头的弹子前面或末尾的弹子后面）插入尽可能少的弹子，使得这\(N\) 颗弹子+插入的所有弹子消失。

输入格式
第一行：\(N,k\)。 第二行：\(c_1,c_2,\cdots,c_n\)。

输出格式
一行，一个整数，表示他至少要插入几颗弹子。

样例1
input

2 5
1 1

output

3

样例2
input

5 3
2 2 3 2 2

output

2

数据范围
\(1≤N≤100,2≤K≤5,1≤c_i≤100\)。

时间限制：2S

空间限制：256MB

是在不知道这题的思路怎么想到的。

定义\(dp_{l,r,x}\)为从\(l\)到\(r\)且\(l\)的左边有\(x\)个和\(c_l\)一样的，我们最少需要加多少个子弹才可以让他们全部消失。

然后有几种选择。首先如果\(k+1\)大于x，我们可以全部归0。否则我们可以再这里再放一个和\(x\)一样的，\(x+1\)

还有一种情况：如果选择两个相同的数，并且把中间的全部消掉，似乎就可以让两边的合起来，变得更小。我们枚举\(l\)到\(r\)中的所有数，如果有与\(c_l\)相同的\(c_i\)，那就递归\(l+1,i-1,0\)和\(i,r,k+1\).

这样在第三种情况中可能会出现超过\(m\)的情况，为了避免，由于超过了m-1，其实就与m-1等价了。所以跳的时候与m-1去min。

大致就是这样了。虽然是dp，但还是记忆化搜索写法比较容易。

#include
#include
const int N=105;
int n,m,a[N],dp[N][N][6];
int min(int x,int y)
{
	return xr)
		return 0;
	if(l==r)
		return m-k-1;
	if(dp[l][r][k]!=-1)
		return dp[l][r][k];
	int ret=2147483647;
	if(k+1>=m)
		ret=dfs(l+1,r,0);
	else
		ret=dfs(l,r,k+1)+1;
	for(int i=l+1;i<=r;i++)
		if(a[i]==a[l])
			ret=min(ret,dfs(l+1,i-1,0)+dfs(i,r,min(m-1,k+1)));
	return dp[l][r][k]=ret;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	printf("%d",dfs(1,n,0));
}