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.
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 #include <bits/stdc++.h> 2 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<len; ++j) 12 for (int i=j; i>=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<len; ++i){ 19 if (s[i] == t[i]){ // 对应位置相同,可以不刷 20 if (i) 21 dp[0][i] = dp[0][i-1]; 22 else 23 dp[0][i] = 0; 24 } 25 else 26 for (int j=0; j<i; ++j) // 寻找当前区间的最优解 27 dp[0][i] = min(dp[0][i], dp[0][j]+dp[j+1][i]); 28 } 29 printf("%d ", dp[0][len-1]); 30 } 31 return 0; 32 }