String painter

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

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
给定两个字符串，每一次可以把某一段刷为同一个字母，求最少刷多少次，可以把字符串1刷为字符串2。
区间dp，先对字符串2进行预处理，然后扫描得出答案。
代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014/3/12 0:09:36
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; char s1[105],s2[105]; int dp[105][105];//dp[i][j]为i~j的刷法 int ans[105],i,j,k,len; int main() { while(~scanf("%s%s",s1,s2)){ len = strlen(s1); memset(dp,0,sizeof(dp)); for(j = 0; j
                
                 =0; i--)//j为尾，i为头 { dp[i][j] = dp[i+1][j]+1;//先每个单独刷 for(k = i+1; k<=j; k++)//i到j中间所有的刷法 if(s2[i]==s2[k]) dp[i][j] = min(dp[i][j],(dp[i+1][k]+dp[k+1][j]));//i与k相同，寻找i刷到k的最优方案 } for(i = 0; i

HDU 2476 区间dp

String painter