欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

hdu6212 Zuma(区间dp)

程序员文章站 2022-04-01 10:24:40
题意:给定串S,只由0和1组成,现在你在玩祖玛游戏,你可以选择一个位置,插入一个0或者一个1,当连续的0或连续的1大于等于3的时候,可以将他们消除,同时将剩余部分拼接,如果拼接之后又出现大于等于3的相同数,继续消除。问最少插入多少个数字可以将所有数都消除。数据范围:|S|<=200,保证一开始不存在大于等于3个的连续相同数字解法:区间dp,先合并相同的数,最后会分成若干段,假设第i段的长度为a[i],令d[i][j]表示消除[i,j]的最小代价,合并有三种方式:1.直接由两个...

题意:

给定串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