HDU 2476 String painter，hdu2476
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.
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 else
23 dp[0][i] = 0;
24 }
25 else
26 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 }
View Code
