HDU 2476 String painter（两次区间dp）-蒲公英云

HDU 2476 String painter（两次区间dp）

String painter

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

题意;从第一个字符串变成第二个字符串最少的步骤，如ddddd abcba 需要三步：1、aaaaa 2、abbba 3、abcba

思路：首先预处理将一个空串变成第二个字符串需要的最少步骤，状态方程dp(i,j)=min(dp(i,k)+dp(k+1,j)) 表示从i到j的最少步骤，

然后就是找第一个字符串变成第二个字符串的最少步骤。

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
int dp[maxn][maxn];
char a[maxn],b[maxn];
int ans[maxn];
int main(){
    while(scanf("%s%s",a+1,b+1)==2){
        memset(dp,0,sizeof(dp));
        int l=strlen(a+1);
        for(int i=1;i<=l;i++)dp[i][i]=1;
        for(int len=2;len<=l;len++)  //长度 
         for(int i=1;i<=l-len+1;i++){  //起点 
             int j=i+len-1;   //终点 
             if(b[i]==b[j])
              dp[i][j]=dp[i][j-1];
              else dp[i][j]=dp[i][j-1]+1;
             for(int k=i;k<j;k++){    //找分割点 
                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);  
             }
         }
         for(int i=1;i<=l;i++)
         ans[i]=dp[1][i];
         for(int i=1;i<=l;i++){
             if(a[i]==b[i])
              ans[i]=ans[i-1]; //当时写成=dp[1][i-1],这个错误找了n久！！！（因为如果有对应位置相同，ans[i-1]！=dp[1][i-1]） 
             else {
                 for(int k=1;k<i;k++)
                 ans[i]=min(ans[i],ans[k]+dp[k+1][i]);
             }
         }
         printf("%d\n",ans[l]);
    }
    return 0;
}