String painter

标签： 区间DP

---

题目描述

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 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.

输出格式

A single line contains one integer representing the answer.

样例

Sample Input
zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd

Sample Output
6
7

题解

一句话概括题目：每次可以选择一段区间涂色，问将一段颜色序列变成另一颜色序列最少多少次。
首先来思考一个简单版本：假设所有位置对应颜色都不同。（比如初始颜色序列为空白）
考虑涂色的性质，如果在最终序列中两个位置颜色相同，s[i]==s[j]，则我们在染j的时候可以顺便把i也染色了。即可以考虑逐次转移法：
f[i,j]表示将[i,j]颜色完全不同染成最终相同颜色的最少次数。
由[i+1,j]推到[i,j]，不过我们要判断[i+1,j]中是否有颜色与s[i]相等，因此还要再[i+1,j]中枚举断点：

f[i][j] = f[i + 1][j] + 1; //假设没有相等的，如果有的话下面也会取min值
for(int m = i + 1; m <= j; m ++)
    if(s[m] == s[i]) f[i][j] = min(f[i][j], f[i + 1][m] + f[m + 1][j]);

接着考虑初始序列可能与最终序列某些位置相同的情况，我们假设f[1,i]表示[1,i]将初始序列染成最终序列颜色的最少次数
如果s1[i]==s2[i],则f[1][i]=f[1][i-1]，因为不需要染色了，否则枚举断点：

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

代码

#include<bits/stdc++.h>
#define N 110
using namespace std;

int cnt;
int a[N], f[N][N];
char s[N], s2[N];

int main()
{
    while(scanf("%s", s2 + 1) != EOF)
    {
        scanf("%s", s + 1);
        int len = strlen(s + 1); cnt = 0;
        for(int i = 1; i <= len; i ++)
            for(int j = i + 1; j <= len; j ++)
                f[i][j] = 1e9;
        for(int i = 1; i <= len; i ++)
            f[i][i] = 1;
        for(int k = 2; k <= len; k ++)
            for(int i = 1; i <= len - k + 1; i ++)
            {
                int j = k + i - 1;
                f[i][j] = f[i + 1][j] + 1;
                for(int m = i + 1; m <= j; m ++)
                    if(s[m] == s[i]) f[i][j] = min(f[i][j], f[i + 1][m] + f[m + 1][j]);
            }
        int tmp = 0;
        for(int i = 1; i <= len; i ++)
        {
            if(s[i] == s2[i]) f[1][i] = f[1][i - 1], tmp = i;
            else
            {
                for(int j = 1; j < i; j ++)
                    f[1][i] = min(f[1][i], f[1][j] + f[j + 1][i]);
            }
        }
        printf("%d\n", f[1][len]);
    }
    return 0;
}