2021.03.20【NOIP提高B组】模拟 总结

区间 DP 专场：愉快爆炸

T1

题目大意

有 n n n 个有颜色的块，连续 k k k 个相同颜色的就可以消掉
现在可以在任意位置插入任意颜色的方块，问最少插入多少个可以全部抵消

题解

先把连续的化成一块，问题变为如何消掉一块。 n u m num num 为个数， c o l o r color color 为颜色
设 F i , j , l e n F_{i,j,len} Fi,j,len​ 表示表示 [ i , j ] [i,j] [i,j] 后面有 l e n len len 个和 j j j 颜色一样的与 j j j 一起消除。
初始 F i , i , l e n = max ⁡ ( 0 , k − n u m i − l e n ) F_{i,i,len}=\max(0,k-num_i-len) Fi,i,len​=max(0,k−numi​−len)
然后 F i , j , l e n = F i , j − 1 , 0 + max ⁡ ( 0 , k − n u m j − l e n ) F_{i,j,len}=F_{i,j-1,0}+\max(0,k-num_j-len) Fi,j,len​=Fi,j−1,0​+max(0,k−numj​−len) 即单独消去
枚举中转点 k ′ k' k′ ， F i , j , l e n = min ⁡ k ′ = i j − 1 F i , k ′ , min ⁡ ( k , l e n + n u m j ) + F k + 1 , j − 1 , 0 ( c o l o r j = c o l o r k ′ ) F_{i,j,len}=\min_{k'=i}^{j-1}F_{i,k',\min(k,len+num_j)}+F_{k+1,j-1,0} (color_j=color_{k'}) Fi,j,len​=mink′=ij−1​Fi,k′,min(k,len+numj​)​+Fk+1,j−1,0​(colorj​=colork′​)
就是先消掉 [ k + 1 , j − 1 ] [k+1,j-1] [k+1,j−1] 然后再将第 j j j 块与 i , k i,k i,k 一起操作
目标： F 1 , n , 0 F_{1,n,0} F1,n,0​

#include<bits/stdc++.h>
using namespace std;
const int N=105; 
int n,K,x[N],cl[N],w[N],tot;
int f[N][N][10];
int main() {
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	cl[1]=x[1],w[1]=tot=1;
	for(int i=2;i<=n;i++) {
		if(x[i]^x[i-1]) {
			++tot,cl[tot]=x[i],w[tot]=1;
		} else ++w[tot];
	}
	memset(f,100,sizeof(f));
	n=tot;
	for(int i=1;i<=n;i++)
		for(int l=0;l<=K;l++)
			f[i][i][l]=max(0,K-w[i]-l);
	for(int l=2;l<=n;l++)
		for(int i=1,j=l;j<=n;i++,j++)
			for(int le=0;le<=K;le++) {
				f[i][j][le]=f[i][j-1][0]+max(0,K-w[j]-le);
				for(int k=i;k<j;k++)
					if(cl[j]==cl[k])
						f[i][j][le]=min(f[i][j][le],f[i][k][min(le+w[j],K)]+f[k+1][j-1][0]);
			}
	printf("%d",f[1][n][0]);
	return 0;
}