[COCI 2010] ZUMA解题报告

解题报告

[COCI 2010] ZUMA解题报告：

题意：给定$n$个珠子，每个珠子有一个颜色$a_i$，每次操作可以在某一个位置插入任意一种颜色的珠子，当存在大于等于$k$个连续的珠子为相同颜色时，这些珠子便会消失，求让所有珠子消失的最小操作数。

为了方便，在这里我们用$t$表示$k$。

首先我们很容易看出来这是一个区间$dp$。

一开始我们想设$f_{i,j}$为消除从$i$到$j$的珠子的最小操作数，然而这行不通，因为无法转移（而且数据范围也提醒你肯定不会这么简单）。

我们设一个三维数组$f_{i,j,k}$代表在前面有$k$个与第一颗珠子相同的珠子时，消除区间$[i,j]$与前面的$k$个珠子的最小操作数。

首先给$f$初始化最大值，然后设置初始值（即区间长度为$1$的情况）：f[i][i][j]=t-j-1;

然后，开始考虑如何转移（枚举区间长度$len$，然后枚举区间起点$i$，即可以得到终点$j$，最后枚举$k$，即为在区间前的珠子数量）：

1. 在这个区间前再加上一颗珠子，然后采取$f_{i,j,k+1}$的消除方式（因此我们需要采取倒推的$dp$顺序）。
2. 如果$i$的颜色与$i+1$的颜色相同的话，可以把第$i$颗珠子视作第$i+1$颗珠子的前缀，即采取$f_{i+1,j,k+1}$的消除方法（因为区间大小是由小至大递推的，所以肯定存在$f_{i+1,j,k+1}$）。
3. 寻找在这个区间内所有与$i$颜色相同的珠子，然后将$i$和这个位置$p$之间所有的珠子按照$f_{i+1,p-1,0}$消除，这样$i$就可以视作第$p$颗珠子的前缀，采取$f_{p,j,k+1}$的消除方式。

最后记得分类讨论一下，如果$k=t-1$的话最好单独拎出来：
1. 第一个转移方式改为$f_{i+1,j,0}$。
2. 第二个转移方式改为$f_{i+1,j,k}$（这个地方有点难懂，其实就是因为只要有连续大于等于$k$个相同颜色的珠子就可以消掉，因此多一颗珠子是没有关系的）。
3. 第三个转移方式的第二个消除方式改为$f_{i+1,j,k}$（原因同上）。

代码：

#include<stdio.h>
#include<string.h>
const int maxn=105,maxt=10;
int i,j,k,m,n,p,t,len;
int a[maxn],f[maxn][maxn][maxt];
inline int min(int a,int b){
    return a<b? a:b;
}
int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&n,&t);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        for(j=0;j<t;j++)
            f[i][i][j]=t-j-1;
    for(len=2;len<=n;len++)
        for(i=1;i+len-1<=n;i++){
            int j=i+len-1;
            f[i][j][t-1]=min(f[i][j][t-1],f[i+1][j][0]);
            if(a[i]==a[i+1])
                f[i][j][t-1]=min(f[i][j][t-1],f[i+1][j][t-1]);
            for(p=i+2;p<=j;p++)
                if(a[i]==a[p])
                    f[i][j][t-1]=min(f[i][j][t-1],f[i+1][p-1][0]+f[p][j][t-1]);
            for(k=t-2;k>=0;k--){
                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][k+1]);
                for(p=i+2;p<=j;p++)
                    if(a[i]==a[p])
                        f[i][j][k]=min(f[i][j][k],f[i+1][p-1][0]+f[p][j][k+1]);
            }
        }
    printf("%d\n",f[1][n][0]); 
    return 0;
}