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?
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进行多少次操作,才能将a变成b。每次操作时将a中任意一段变成任意一个字母所组成的段。#include<stdio.h> #include<string.h> int min(int a,int b) { return a>b?b:a; } int main() { int dp[105][105],ans[105]; char a[105],b[105]; while(scanf("%s%s",a,b)>0) { int len=strlen(a); memset(dp,0,sizeof(dp)); for(int r=0;r<len;r++) for(int i=0;i<len-r;i++) { int j=i+r; dp[i][j]=dp[i+1][j]+1; for(int k=i+1;k<=j;k++) if(b[i]==b[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(a[i]==b[i]) { if(i==0)ans[i]=0; else ans[i]=ans[i-1]; } else{ for(int k=0;k<i;k++) ans[i]=min(ans[i],ans[k]+dp[k+1][i]); } printf("%d\n",ans[len-1]); } }