【UVA1437】String painter

题意描述

现在，有两个用小写英文字母组成的等长字符串，设其分别为$\text{A} , \text{B}$。

与此同时，你有一个强大的字符串刷子。在这把刷子的帮助下，你可以将一个字符串的一个字串中的字符全部刷成任何你想要的字符。

也就是说，用刷子刷过的字串就变成用同一个字母组成的了。

现在你想要用这一把刷子把字符串$\text{A}$刷成$\text{B}$，但这刷子比较重，你并不想很多次的拿起它。

所以你要写一个程序，求出拿起刷子的最少次数。

---

输入格式

输入包含多组数据，每一组数据包括两行，分别是两个字符串$\text{A}$与$\text{B}$;

---

输出格式

对于每组数据，输出一行，一个整数，表示最小次数。

---

Input & Output ‘s examples

Input ‘s eg

hfcnndeziymohaewnrbmquyhigwm
bcbysbjvxbzvmspshggrzaukbipm
jmmeqimjobpxyavjneyvyuuhhwiqowmme
kmpgpviubhzrjkezqqoilsuwgedctxkxl
ikynfrlcsltkrbdkdqpirtdnajhzhbhipeqtyxvskhkti
qmziwxbbjzjfymrzvflthsbaqgdoqmiduiudviqzztclb
vwysgqniecydcycqk
cqgudqbkgcsvimpdj
mcrrqwfegpnukyuk
vezrniuriscgtcth
rdjtgk
wzfycu
nwxqfdtigwj
rrhcndwcohx
knjmrwlwxfroyppgxhrknntrvbcqjrranufutrginldqydsjsfyjqfyqq
lghrdjsgvbffgfpclqmrzzoniyhlsoisgpbfdqpiblsbtirrbdjdjxsuy
nujagihmgqvwiwvbmbe
pnxicvskosnzneztzhd
bzjvffvyv
mnvjbgwdw

Output ‘s eg

20
26
33
15
13
6
8
43
15
8

---

数据范围和约定

设$t$为数据组数，$|s|$为字符串$s$的长度。

对于$100\%$的数据，保证$1 \leq t \leq 100 , 1 \leq |\text{A}|, |\text{B}| \leq 100$，且保证$|\text{A}| = |\text{B}|$。

---

分析

题目的大体思路并不难想，就是一个区间$\text{dp}$

但状态的设计比较困难。由于$\text{A}$与$\text{B}$中字符的不确定性，我们难以定义状态并写出转移方程。

因此，我们可以换个角度，先考虑其弱化版本，即$\text{A}$为空串时的情况。

设$f[i][j]$表示将空串$\text{A}$的第$i$到$j$位刷的与$\text{B}$相同所需要的最少次数。显然，当$i = j$时，$f[i][j] = 1$。

当$i ≠ j$时，则看$B$的第$i$位与第$j$位是否相同。若相同的话，则有：

$$f[i][j] = min(f[i + 1][j] , f[i][j - 1])$$

否则的话，我们采用类似于$\text{floyd}$的套路，枚举中间点$k$，则有：

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

现在我们已经解决了$\text{A}$为空串时的情况。若$\text{A}$不为空串，则$A$的第$i$位与$B$的第$i$位可能相同，此时$f[i][i] = 0$。

则我们设$g[i]$表示$\text{A}$从第$1$到$i$位与$\text{B}$从$1$到$i$位相同所需要的最少次数。初始状态下，有$g[i] = f[1][i]$。

显然，$\text{A}$的第$i$位与$\text{B}$的第$i$位相同时，有$g[i] = g[i - 1]$。

若不同的话，和上面的套路一致，枚举中间点$k$，则有：

$$g[i] = min(g[i] , g[k] + f[k + 1][i])$$

最后别忘了多组数据，每次计算之前都需要清空

时间复杂度为$O(t \times n^2)$，足以通过本题。

剩下的见代码注释。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

char s1[155] , s2[155];
int f[155][155] , g[155];   

//f[i][j] 将空串A的 i 到 j 位刷的与B相同所需要的最少次数
//g[i]    A从 1 到 i 位与B从 1 到 i 位相同所需要的最少次数

namespace solve{
    int main(){
        int len = strlen(s1 + 1);
        clean(f , 0x3f3f3f3f);
        rep(i , 0 , len){
            f[i][i] = 1;
        }
        rep(k , 1 , len){
            for(int i = 1; i + k <= len; i ++){
                int j = i + k;
                if(s2[i] == s2[j]){
                    f[i][j] = min(f[i + 1][j] , f[i][j - 1]);
                }
                else{
                    rep(l , i , j){
                        f[i][j] = min(f[i][j] , f[i][l] + f[l + 1][j]);
                    }
                }
            }
        }
        clean(g , 0x3f3f3f3f);
        g[0] = 0;
        rep(i , 1 , len){
            g[i] = f[1][i];
            if(s1[i] == s2[i]){
                g[i] = min(g[i] , g[i - 1]);
            }
            else{
                rep(l , 1 , i){
                    g[i] = min(g[i] , g[l] + f[l + 1][i]);
                }
            }
            g[i] = min(g[i] , f[1][i]);
        }
        return g[len];
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    while(scanf("%s%s" , s1 + 1 , s2 + 1) == 2) printf("%d\n" , solve :: main());
    //多组数据时建议写为函数或namespace , 便于调试。
    return 0;
}

---

THE END