String painter
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3639 Accepted Submission(s): 1697
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
Recommend
lcy
题目大意: 给定两个等长度的字符串,有一种刷新字符串的方法,它能够将一段字符串刷成同一个字符(任意字符)。 现在要你使用这种方法,使得第一个字符串被刷成第二个字符串,问你最少需要刷多少次?
解题思路:显然这是一道区间DP的题。设dp[i][j]表示区间[i,j]内最少需要刷多少次。直接确定状态转移方程不太好确定,所以我们需要考虑直接将一个空串刷成第二个字符串,然后再与第一个字符串去比较。这样, 如果每个字符都是单独刷新,则dp[i][j] = dp[i+1][j]+1, 如果在区间[i+1,j]之间有字符与t[i]相同,则可以将区间分为两个区间,分别为[i+1,k]和[k+1,j],考虑一起刷新。详见代码。
附上AC代码:
1 #include2 using namespace std; 3 const int maxn = 105; 4 char s[maxn], t[maxn]; 5 int dp[maxn][maxn]; 6 7 int main(){ 8 while (~scanf("%s%s", s, t)){ 9 memset(dp, 0, sizeof(dp));10 int len = strlen(s);11 for (int j=0; j =0; --i){13 dp[i][j] = dp[i+1][j]+1; // 每一个都单独刷14 for (int k=i+1; k<=j; ++k)15 if (t[i] == t[k]) // 区间内有相同颜色,考虑一起刷16 dp[i][j] = min(dp[i][j], dp[i+1][k]+dp[k+1][j]);17 }18 for (int i=0; i