hdu6212 Zuma（区间dp）

题意：

给定串S，只由0和1组成，
现在你在玩祖玛游戏，你可以选择一个位置，插入一个0或者一个1，
当连续的0或连续的1大于等于3的时候，可以将他们消除，
同时将剩余部分拼接，如果拼接之后又出现大于等于3的相同数，继续消除。
问最少插入多少个数字可以将所有数都消除。

数据范围：|S|<=200，保证一开始不存在大于等于3个的连续相同数字

解法：

区间dp,
先合并相同的数,最后会分成若干段,
假设第i段的长度为a[i],
令d[i][j]表示消除[i,j]的最小代价,
合并有三种方式:
1.直接由两个子区间合并,d[i][k]+d[k+1][j]
2.当i和j数字相同的时候,可以先将中间消除,然后合并a[i]和a[j],
d[i+1][j-1]+(a[i]+a[j]<3)
3.i和j的中间存在一个k,满足i,k,j数字相同,
且a[i]+a[k]<3,a[k]+a[j]<3,
此时可以将a[i+1][k-1]和a[k+1][j-1]消除,
然后i,k,j三者合并消除

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=205;
int d[maxm][maxm];
int a[maxm];
char s[maxm];
int n;
signed main(){ 
    int T;cin>>T;
    signed cas=1;
    while(T--){ 
        scanf("%s",s+1);
        n=strlen(s+1);
        //合并连续的
        int m=0;
        for(int i=1;i<=n;i++){ 
            if(s[i]==s[i-1])a[m]++;
            else a[++m]=1;
        }
        //init
        for(int i=1;i<=m;i++){ 
            for(int j=i;j<=m;j++){ 
                d[i][j]=1e9;
            }
        }
        for(int i=1;i<=m;i++){ 
            d[i][i]=3-a[i];
        }
        //dp
        for(int len=2;len<=m;len++){ 
            for(int i=1;i<=m;i++){ 
                int j=i+len-1;
                if(j>m)break;
                for(int k=i;k<j;k++){ //由两个子区间合并得来
                    d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
                }
                if(len%2){ //a[i]和a[j]的数一样,先消除中间
                    if(a[i]+a[j]==2){ 
                        d[i][j]=min(d[i][j],d[i+1][j-1]+1);
                    }else{ 
                        d[i][j]=min(d[i][j],d[i+1][j-1]);
                    }
                    if(a[i]+a[j]<4){ //找i,k,j消除
                        for(int k=i+2;k<j;k+=2){ 
                            if(a[k]==1){ 
                                d[i][j]=min(d[i][j],d[i+1][k-1]+d[k+1][j-1]);
                            }
                        }
                    }
                }
            }
        }
        //output
        printf("Case #%d: ",cas++);
        cout<<d[1][m]<<endl;
    }
    return 0;
}

本文地址：https://blog.csdn.net/weixin_44178736/article/details/108569992