题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2476
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
题目翻译:
有两个长度相等的字符串 A 和 B。两个字符串由小写字母组成。现在你有一个强大的字符串画家。在画家的帮助下,您可以将字符串的字符段更改为所需的任何其他字符。也就是说,使用画家后,该段仅由一种字符组成。现在,您的任务是使用字符串绘制器将 A 更改为 B。最低操作数是多少?
输入
输入包含多个案例。每个大小写由两行组成:
第一行包含字符串A。
第二行包含字符串B。
两个字符串的长度不会大于100。
输出
一行包含一个表示答案的整数。
如果直接去把A串刷成B串,很难找到状态转移方程,不妨先从空白串开始刷B串,之后再进行A与B串的匹配。
两个状态转移方程,比较巧妙,详细过程参考代码。
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char s1[105],s2[105];
int dp[105][105];
int ans[105];
int main(int argc, char** argv) {
while(~scanf("%s%s",s1,s2)){
int len=strlen(s1);
memset(dp,0,sizeof(dp));
/*
于是,用dp[i][j]记录从把i~j区间的空串变化到目标串,
初始化方程:dp[i][j] = dp[i+1][j] + (t[i]==t[j]?0:1);
0的意思是,i不用考虑了,因为可以在刷j时“顺便”把它刷了,注意
if(t[i] == t[j]) dp[i][j] = dp[i+1][j-1]+1是不对的,这样答案是偏大的
变化方程:if(t[i] == t[k])
dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
这样有了dp值后,再来求这个题目的ans,ans[i]代表0~i初始串变到目标串所需的最少步数
对ans[i],枚举出所有的情况即可
*/
for(int j = 0;j<len;++j){
for(int i = j;i>=0;--i){
dp[i][j]=dp[i+1][j]+1;
for(int k = i+1;k<=j;++k)
if(s2[i]==s2[k])
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
}
}
for(int i = 0;i<len;++i) ans[i]=dp[0][i];
for(int i = 0;i<len;++i){
if(s1[i]==s2[i]) ans[i]=ans[i-1];
else {
for(int j = 0;j<i;++j)
ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
}
}
printf("%d\n",ans[len-1]);
}
return 0;
}