这道题很明显是一个dp问题
我们先考虑基本状态应该是f[i][j]表示[i,j]消掉需要添加多少个
但是我们发现这不太好转移
所以我们需要记录更多的信息
我们设计状态f[i][j][k]表示，区间[i,j]，在i前面加上k个a[i]，把整个区间消掉需要的步数
那么转移就是
f[i][j][k]=f[i][j][k+1]+1(k<K−1)
f[i][j][k]=f[i+1][j][0](k=K−1)
f[l][r][k]=f[l+1][j−1][0]+f[j][r][min(k+1,K−1)](a[l]=a[j])
为什么呢？
很多人可能看不懂第一个式子（比如说我）
他的意思是，他需要比在前面放k+1个的时候再多一步，因为这个情况是想让他被消掉，但是可能k个消不掉，所以我们看k+1个行不行
第二个式子就是当k=K−1时肯定可以把a[i]消掉，所以我们看a[i+1]的情况
第三个式子就是找相同的，因为前后有相同的的时候我们可以先把中间的给消掉
由于循环顺序不好确定，我们可以打一个记搜
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <climits>
# include <iostream>
# include <string>
# include <queue>
# include <stack>
# include <vector>
# include <set>
# include <map>
# include <cstdlib>
# include <ctime>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=105;
const int inf=0x7fffffff;
const double eps=1e-7;
template <typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,K;
int a[N];
int f[N][N][N];
int dfs(int l,int r,int k){
if(f[l][r][k]!=-1)return f[l][r][k];
if(l>r)return 0;
int res=INT_MAX;
if(k<K-1)res=min(res,dfs(l,r,k+1)+1);
if(k==K-1)res=min(res,dfs(l+1,r,0));
Rep(i,l+1,r)
if(a[l]==a[i])res=min(res,dfs(l+1,i-1,0)+dfs(i,r,min(k+1,K-1)));
f[l][r][k]=res;
return res;
}
int main()
{
memset(f,-1,sizeof(f));
read(n),read(K);
Rep(i,1,n)read(a[i]);
printf("%d\n",dfs(1,n,0));
return 0;
}