题目
现在有一行 n 个弹子,每个弹子都有颜色,每次可以让连续
至少 k 个相同颜色的弹子消失,两边合在一起。求插入弹子数量
的最小值,使得所有弹子消失。
n ≤ 100,k ≤ 5。
思路
设 fi,j,k 表示 [i, j] 中的弹子,已经在前面插入了 k 个与 i 同
色的弹子,消去的最小代价。
转移有三种:在前面插入一个弹子、消去当前弹子、消去中
间一段使 i 与后面合并。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=177;
int n,k,a[N];
int f[N][N][10];
int dfs(int l,int r,int x)
{if (f[l][r][x]!=-1){return f[l][r][x];}if (l>r){return 0;}if (l==r){return k-x-1;}int ans=0;if (x<k-1){ans=dfs(l,r,x+1)+1;}else{ans=dfs(l+1,r,0);}for (int i=l+1;i<=r;++i){if (a[i]==a[l]){ans=min(ans,dfs(l+1,i-1,0)+dfs(i,r,min(k-1,x+1)));}}f[l][r][x]=ans;return ans;
}
int main()
{cin>>n>>k;for (int i=1;i<=n;++i){cin>>a[i];}memset(f,-1,sizeof(f));cout<<dfs(1,n,0);return 0;
}