程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu2476——String painter

hdu2476——String painter

編輯：C++入門知識

hdu2476——String painter

String painter

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1834 Accepted Submission(s): 814

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 | We have carefully selected several similar problems for you: 2480 2481 2478 2482 2475

Statistic | Submit | Discuss | Note

區間dp，這題很特殊啊，要先考慮從空串變成第二個串，然後再利用這個信息去計算第一個串變成第二個串的最少次數

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 110;
const int inf = 0x3f3f3f3f;
int dp[N][N];
int f[N];
char stra[N], strb[N];

int main()
{
	while(~scanf("%s%s", stra + 1, strb + 1))
	{
		int n = strlen(stra + 1);
		memset (dp, 0, sizeof(dp));
		memset (f, inf, sizeof(f));
		for (int i = 1; i <= n; ++i)
		{
			dp[i][i] = 1;
		}
		for (int i = n; i >= 1; --i)
		{
			for (int j = i + 1; j <= n; ++j)
			{
				dp[i][j] = dp[i + 1][j] + 1;
				for (int k = i + 1; k <= j; ++k)
				{
					if (strb[k] == strb[i])
					{
						dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);
					}
				}
			}
		}
		f[0] = 0;
		for (int i = 1; i <= n; ++i)
		{
			f[i] = dp[1][i];
		}
		for (int i = 1; i <= n; ++i)
		{
			if (stra[i] == strb[i])
			{
				f[i] = f[i - 1];
			}
			else
			{
				for (int j = 0; j < i; ++j)
				{
					f[i] = min(f[i], f[j] + dp[j + 1][i]);
				}
			}
		}
		printf("%d\n", f[n]);
	}
	return 0;
}