DQS DQS

[hdu2746]String painter 区间DP

in 简单DP,算法,DPread (187) 文章转载请注明来源!

Problem Description

There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?

Input

Input contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.

Output

A single line contains one integer representing the answer.

Sample Input

zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd

Sample Output

6
7

Source

2008 Asia Regional Chengdu

Recommend

lcy | We have carefully selected several similar problems for you: 2480 2481 2478 2482 2475


一眼区间dp。

然后…然后不太会做…
本来想像计算连续子段数那样合并时处理跨越两区间时的染色数,然而因为之后的染色会覆盖之前的,所以并不知道应该减去多少。
然后有一个想法:减去的数量等于断点向左、向右遇到共色点对的数量。于是想处理一个g[i][j]表示从第i个数断开,向左向右j个格子的同色点对数。

然后发现这个g数组超难求,并且两个字符串也不会处理,巨麻烦…

然后就去搜了题解

还是区间dp。首先处理空串到s2,再处理s1到s2。

空串到s2:
注意形如aXXXaXXX的字符串,可以先上底色a(这个步骤已经被f[i+1][k]统计过了),或者说是这个字符串等价于XXXaXXX,于是f[i][j]可以由f[i+1][k]+f[k+1][j]转移过来。
当然若没有这种情况,答案显然是f[i+1][j]+1.

s1到s2:
s1和空串的不同就是有些原串需要涂的地方它不需要涂。
于是若s1[i]==s2[i],可以直接视为这个点不存在,舍去。因为空白串到s2一定会刷这个颜色,而s1至少可以把这一次操作省掉。
并且需要用之前的ans更新一下,这个很容易理解。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
const int SZ = 110;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int f[SZ][SZ],ans[SZ];
char s1[SZ],s2[SZ];

int main()
{
    while(~scanf("%s%s",s1 + 1,s2 + 1))
    {
        int n = strlen(s1 + 1);
        memset(f,0,sizeof(f));
        for(int i = 1;i <= n;i ++)
            f[i][i] = 1;

        for(int i = n;i >= 1;i --)
            for(int j = i + 1;j <= n;j ++)
            {
                f[i][j] = f[i + 1][j] + 1;
                for(int k = i + 1;k <= j;k ++)
                    if(s2[i] == s2[k])
                        f[i][j] = min(f[i][j],f[i + 1][k] + f[k + 1][j]);
            }

        for(int i = 1;i <= n;i ++) ans[i] = f[1][i];
        for(int i = 1;i <= n;i ++)
        {
            if(s1[i] == s2[i]) ans[i] = ans[i - 1];
            for(int j = 1;j < i;j ++)
                ans[i] = min(ans[i],ans[j] + f[j + 1][i]);
        }

/*        for(int i = 1;i <= n;i ++,puts(""))
            for(int j = 1;j <= n;j ++)
                printf("%d ",f[i][j]);
        for(int i = 1;i <= n;i ++) printf("%d ",ans[i]); puts("");*/
        printf("%d\n",ans[n]);
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

简单DP算法DP
最后由DQS修改于2017-11-23 19:30
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆