CSU-ACM2017暑假训练9-区间DP G - String painter

G - String painter

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 #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <string> using namespace std; int dp[1004][1004], ans[104]; int main(){ #ifdef TEST freopen("test.txt", "r", stdin); #endif // TEST string strA, strB; while(cin >> strA >> strB){ for(int i = 0; i < 1004; i++) dp[i][i] = 1; for(int len = 1; len < strB.length(); len++){ for(int s = 0, e = len; e < strB.length(); s++, e++){ dp[s][e] = dp[s][e-1]+1; for(int k = s; k < e; k++) if(strB[k] == strB[e]) dp[s][e] = min(dp[s][e], dp[s][k]+dp[k+1][e-1]); } } for(int i = 0; i < strB.length(); i++) ans[i] = dp[0][i]; for(int i = 0; i < strA.length(); i++){ if(strA[i]!=strB[i]) for(int j = 0; j < i; j++) ans[i] = min(ans[i], ans[j]+dp[j+1][i]); else{ if(i == 0) ans[i] = 0; else ans[i] = ans[i-1]; } } cout << ans[strB.length()-1] << endl; } return 0; }