满分做法:
\(dp[i][j][k]\)表示在区间\([i-j]\)加上一段长度为\(k\),且数字和\(a[i]\)相同的序列,要消除这整个序列所需要的最小操作次数。
1.普通情况:我们可以在当前状态继续在前面加一个与\(a[i]\)相同的数即:\(dp[i][j][k]=dp[i][j][k+1]+1\)。
(1):"+1"是由于添加一个数就是一次操作。
(2):此时前面一共有k+1个与Ai相同的数。
2.当此时\(k=K-1\):那么我们可以消除前K个啦,且i前进一位,即:\(dp[i][j][k]=dp[i+1][j][0]\)。
3.如果在区间\([i,j]\)中在\(a[i]\)后面有和\(a[i]\)相同的的数,根据规则,我们可以先消掉他俩之间的数,再消掉剩下合并的一段,即:
\(dp[l][r][k]=dp[l+1][j-1][0]+dp[j][r][min(k+1,K-1)]\)（a[l]==a[j]）,取min方便和方式2结合。
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int n,k;
int a[110];
int dp[110][110][110];//dp[i][j][k]表示区间i-j加上一段长度为k,且数字和Ai相同的序列,要消除这整个序列所需要的最小操作次数。
int dfs(int l,int r,int add)
{
if(dp[l][r][add]!=-1) return dp[l][r][add];
if(l>r) return 0;
if(l==r) return k-add-1;//还要补这么多弹
int res=2147483647;
if(add==k-1) res=min(res,dfs(l+1,r,0));
if(add<k-1) res=min(res,dfs(l,r,add+1)+1);
for(int j=l+1;j<=r;j++)
{
if(a[l]==a[j])
{
res=min(res,dfs(l+1,j-1,0)+dfs(j,r,min(add+1,k-1)));//后面取add+1是因为a[l]也算作加上的长度
}
}
dp[l][r][add]=res;
return res;
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("%d\n",dfs(1,n,0));
return 0;
}