HDU 2476 String painter（两次区间dp）

ゝ一世哀愁。 2024-02-17 19:36 9阅读 0赞

## 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;
    }