容易想到区间 dp,考虑设计状态。
首先如果只有 \(l,r\) 两维的话,是无法转移的。然后发现 \(m\) 是转移的一个必要的条件,可加入 \(m\) 这一维。由于是区间 dp,所以只需考虑向左或向右加珠子,不妨令 \(f_{i,j,k}\) 消除 \([i,j]\) 以及 \(i\) 前面的 \(k\) 颗珠子的的最少步数。
\(f\) 首先要赋为一个极大值,初始条件显然为 \(f_{i,i,j}=K-1-j\)。
转移需要分类讨论一下。
首先,如果 \(a_i = a_{i+1}\),就可以从 \(f_{i+1,j,k+1}\) 递推而来。
然后也可以由 \(f_{i,j,k+1}\) 递推得到,即在前面多一颗珠子。还有一个就是找到某点 \(p\),满足 \(a_i=a_p\),此时就是 \(f_{i+1,p-1,0}+f_{p,j,k+1}\)。
即 \(f_{i,j,k}=\min\{f_{i+1,j,k+1},\min\limits_{p=i+1,a_i=a_p}^{j}\{f_{i+1,p-1,0}+f_{p,j,k+1}\}, f_{i,j,k+1}+1\}\)。
代码:
const int N=110;
int n,m;
int a[N],f[N][N][N];
int main(){
memset(f,0x3f,sizeof(f));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=0;j<m;j++)
f[i][i][j]=m-1-j;
}
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
for(int k=m-1;k>=0;k--){
if(k==m-1)
f[i][j][k]=min(f[i][j][k],f[i+1][j][0]);
else
f[i][j][k]=min(f[i][j][k],f[i][j][k+1]+1);
if(a[i]==a[i+1])
f[i][j][k]=min(f[i][j][k],f[i+1][j][min(k+1,m-1)]);
for(int l=i+1;l<j;l++)
if(a[i]==a[l+1])
f[i][j][k]=min(f[i][j][k],f[i+1][l][0]+f[l+1][j][min(k+1,m-1)]);
}
}
cout<<f[1][n][0]<<endl;
return 0;
}