Mayflyyh
Mayflyyh
MayFlyyh's Blog
HDU 2476 String painter

题意:给你一个由小写字母组成的串S,让你变成由小写字母组成的串F,你可以每次将一个区间变成任意一个小写字母,后来的操作可以覆盖原来的区间,求最小操作次数。

|S|<=200


本题与bzoj1260很相似,bzoj1260是给你一个空白串让变成F,本题是在S上修改

bzoj1260的做法:

dp[i][j]表示从i到j涂成F[i~j]的最小花费次数

初始化 dp[i][i]=1

if(F[i]==F[j])
dp[i][j]=min(dp[i+1][j],dp[i][j-1])

表示如果i和j颜色一样,涂i或j的时候把另一个一起涂了就可以了

dp[i][j]=min(dp[i][j],dp[i][k]+[k+1][j])

这个就是普通枚举

HDU这道题是在原串上修改,那么代价应该是小于等于在空白上添加的,开始时总想用一个状态表示,但始终没有办法。看题解原来是做两次DP。一次就如bzoj上的,后一次是

F[i]表示到i为止需要的代价

if(F[i]==S[i]) F[i]=F[i-1]
F[i]=min(F[i],F[j]+dp[j+1][i]) 0<=j<i

CODE:

#include<bits/stdc++.h>
char goal[110],now[110];
int dp[110][110],f[110];
int main(){
    while(scanf(" %s %s",now+1,goal+1)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        int len=strlen(goal+1);
        for(int i=1;i<=len;++i) dp[i][i]=1;
        for(int i=2;i<=len;++i){
            for(int l=1,r=l+i-1;r<=len;++l,r=l+i-1){
                dp[l][r]=0x3f3f3f3f;
                if(goal[l]==goal[r]){
                    dp[l][r]=std::min(0x3f3f3f3f,std::min(dp[l+1][r],dp[l][r-1]));
                }
                else{
                    for(int mid=l;mid<=r;++mid){
                        dp[l][r]=std::min(dp[l][r],dp[l][mid]+dp[mid+1][r]);
                    }
                }
            }
        }
        f[1]=now[1]==goal[1]?0:1; 
        for(int i=2;i<=len;++i){
            f[i]=0x3f3f3f3f;
            if(now[i]==goal[i]){
                f[i]=f[i-1];
            }
            else
                for(int j=0;j<=i-1;++j){
                    f[i]=std::min(f[i],f[j]+dp[j+1][i]);    
                }
        }
        printf("%d\n",f[len]);
    }
}

本文链接:http://www.mayflyyh.com/archives/310
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      HDU 2476 String painter
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

HDU 2476 String painter
题意:给你一个由小写字母组成的串S,让你变成由小写字母组成的串F,你可以每次将一个区间变成任意一个小写字母,后来的操作可以覆盖原来的区间,求最小操作次数。 |S|<=200 …
扫描二维码继续阅读
2018-08-14