hdu 2476 String painter

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，一次能夠把第一個字元串中的一段區間内的全部字母都換成同一個字母（這個字母能夠是随意一個），問最少運作多少次操作，才幹将第一個字元串s1轉換成第二個字元串s2.

思路：

先将空白串變為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]);

處理完後，我們就要看s1須要噴刷多少次到s2了，s1比空白串的長處在哪裡呢？在于s1有與s2同樣的字元，這些字元能夠不用個刷本身就與s2同樣，用res[i]記錄1~i區間第二個字元串得出的噴刷次數，假設第一個字元串的i位置與第二個字元串的i位置同樣，那麼這個位置就不用噴刷了，res[i]=res[i-1],假設不同樣，就要就要借助一個位于1~(i-1)區間内的變量來切割開，res[i]=min(res[i],res[j]+dp[j+1][i])。

代碼：