String painter

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1257 Accepted Submission(s): 532

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

1 //46MS    292K    1034 B    C++ 2 //区间DP,给两个字符串s1、s2,求将s1变成s2的最少操作步数的刷法 3   4 /* 5 第一步：假设A,B完全不等，没有位置上的字符相等，那么可以进行区间dp 6  7 dp[i][j]表示从i到j最少需要多少步 8  9 dp[i][j]=dp[i+1][j]+1;10 11 dp[i][j]=MIN(dp[i][j],dp[i+j][k]+dp[k+1][j])  ---(i+1~j)12 13 第二步：考虑s1和s2某些位置会相等14 15 ans[i]=dp[0][i]  (if(s1[0]==s2[0]) ans[0]=0;)16 17 ans[i]=ans[i-1]   s1[i]==s2[i]18 19 ans[i]=Min(ans[i],ans[j]+dp[j+1][i]) 0<=j20 21 22 ans[i]记录 0~i 的最优刷法步数 23 */24 25 #include
     
      26 #include
      
       27 int dp[105][105];//dp[i][j]为i~j的刷法 28 char s1[105],s2[105];29 int ans[105],i,j,k,len;30 int Min(int a,int b)31 {32     return a
       
        =0;i--){42                 dp[i][j]=dp[i+1][j]+1; //每个单独刷 43                 for(int k=i+1;k<=j;k++){  //i~j间最优刷法 44                     if(s2[i]==s2[k])45                         dp[i][j]=Min(dp[i][j],dp[i+1][k]+dp[k+1][j]); 46                 }47                 //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]); 48             }49         }50         for(int i=0;i