String painter
Time Limit: 5000/2000 MS (
Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1529 Accepted Submission(s): 680
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 2008 Asia Regional Chengdu
题意： 有两个字符串长度相同，现在有一个painter，一次可以把第一个字符串中的一段区间内的所有字母都换成同一个字母（这个字母可以是任意一个），问最少执行多少次操作，才能将第一个字符串转换成第二个字符串
思路： 先将空白串变为s2，dp[i][j]-将i~j刷为目标串所需要的步数。 dp[i][j]=dp[i][j-1]+1; j单独刷 当s[j]==s[k]时，j可以借助刷k的时候一起刷，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);
然后后面的其实我也还不是太懂，先写下来后面在慢慢看，区间dp还理解的不够透彻。 处理完前面的后后，我们就要看第一个字符串究竟需要喷刷多少次了，用res[i]记录1-i区间第二个字符串得出的喷刷次数，如果第一个字符串的i位置与第二个字符串的i位置相同，那么这个位置就不用喷刷了，res[i]=res[i-1],如果不相同，就要就要借助一个位于1-(i-1)区间内的变量来分割开
代码：
#include
#include
#include
#include
#include
#include
#include