2014
01-26

# 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 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.

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.

zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd

6
7

//============================================================================
// Name        : HDU.cpp
// Author      :
// Version     :
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int MAXN=110;
int dp[MAXN][MAXN];
char str1[MAXN],str2[MAXN];
int ans[MAXN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%s%s",str1,str2)==2)
{
int n=strlen(str1);
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
dp[i][j]=j-i+1;
//先直接DP求出从空白串变成str2
for(int i=n-2;i>=0;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(str2[i]==str2[k])
dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
}
for(int i=0;i<n;i++)
{
ans[i]=dp[0][i];
if(str1[i]==str2[i])
{
if(i==0)ans[i]=0;
else ans[i]=ans[i-1];
}
for(int j=0;j<i;j++)
ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
}
printf("%d\n",ans[n-1]);
}
return 0;
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

3. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。