首页 > 代码库 > LA 4394
LA 4394
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
令dp[l][r] 为l到r区间从空串刷成b串所需的最少次数
则dp[l][r] = min(dp[l][k] + dp[k + 1][r])
如果 b[l] == b[r] dp[l][r] = min(dp[l][r], dp[l][r - 1])
最后设f[i]为1 到 i从a串刷到b串的最少次数(下标从1开始）
则 f[i] = min(f[j] + dp[j][i - 1])
如果a[i] == b[i]则 f[i] = min(f[i], f[i - 1])
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 8 using namespace std; 9 10 #define read() freopen("sw.in", "r", stdin)11 12 const int MAX = 105;13 char a[MAX], b[MAX];14 int dp[MAX][MAX];15 int f[MAX];16 17 void solve() {18 int n = strlen(a);19 for (int len = 1; len <= n; ++len) {20 for (int l = 0; l + len - 1 < n; ++l) {21 int r = l + len - 1;22 dp[l][r] = len;23 if (l == r) {24 dp[l][r] = 1;25 continue;26 }27 for (int k = l; k <= r; ++k) {28 if (k + 1 > r) continue;29 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);30 }31 if (b[l] == b[r]) dp[l][r] = min(dp[l][r - 1], dp[l][r]);32 //printf("l = %d r = %d %d\n", l, r, dp[l][r]);33 }34 }35 36 for (int i = 0; i < n; ++i) {37 f[i + 1] = dp[0][i];38 if (a[i] == b[i]) f[i + 1] = min(f[i + 1], f[i]);39 for (int j = 0; j < i; ++j) {40 if (j + 1 > i) continue;41 f[i + 1] = min(f[i + 1], f[j + 1] + dp[j + 1][i]);42 }43 }44 45 //for (int i = 0; i < n; ++i) printf("%d ", f[i]);46 printf("%d\n", f[n]);47 48 49 }50 51 int main()52 {53 54 int t;55 //read();56 while (scanf("%s%s", a, b) != EOF) {57 solve();58 }59 //cout << "Hello world!" << endl;60 return 0;61 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。