首页 > 代码库 > HDU 2476 String painter
HDU 2476 String painter
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
2008 Asia Regional Chengdu
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 else23 dp[0][i] = 0;24 }25 else26 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\n", dp[0][len-1]);30 }31 return 0;32 }
HDU 2476 String painter
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。