BZOJ1032:[JSOI2007]祖码Zuma dp

思路:

首先将颜色分段.

令\(f[i][j]\)表示第\(i\)段到第\(j\)段全部清除最小的代价.

转移一:

\[f[i][j]=\min_{k=i}^{j-1}f[i][k]+f[k+1][j]\]

转移二:

\(i=j\),直接转移

转移三:

\(col[i]=col[j]\),\(f[i][j]=f[i+1][j-1]+blabla...\)

可是这样是不一定对的.

(做到这里在OJ上就可以AC了.)

他不能处理三个离散的珠子合并的情况.

比如1 2 2 1 3 3 1.

正确答案应该是2.

我们加一步判断,如果区间两端都是只有一个的话,尝试在区间中寻找同样颜色的,然后合并.

由于数据问题,这样判断是会WA的.但是这应该是正确答案.

(在OJ上可以AC的代码)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 510
int a[N],col[N],cnt[N],id;
 
int f[N][N];
int main(){
    int n;scanf("%d",&n);
    register int i,j,k,p;
    for(i=1;i<=n;++i)scanf("%d",&a[i]);
    for(i=1;i<=n;){
        col[++id]=a[i],cnt[id]=1;
        for(j=i;j!=n&&a[j]==a[j+1];++j,++cnt[id]);
        i=j+1;
    }
     
    for(k=1;k<=id;++k){
        for(i=1;i+k-1<=id;++i){
            j=i+k-1;
            if(i==j)f[i][j]=(cnt[i]>=3?1:(3-cnt[i]));
            else{
                f[i][j]=~0U>>1;
                for(p=i;p<j;++p)f[i][j]=min(f[i][p]+f[p+1][j],f[i][j]);
                if(k>=3&&col[i]==col[j])f[i][j]=min(f[i][j],f[i+1][j-1]+((cnt[i]+cnt[j]>=3)?0:(3-cnt[i]-cnt[j])));
            }
        }
    }
     
    printf("%d\n",f[1][id]);
    return 0;
}