HDU 2476 String painter（两次区间dp）

2019-11-06 07:06:50

字体：大中小

来源：转载

供稿：网友

String painter

PRoblem DescriptionThere 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? InputInput 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. OutputA single line contains one integer representing the answer. Sample Input

zzzzzfzzzzzabcdefedcbaababababababcdcdcdcdcdcd Sample Output67
题意;从第一个字符串变成第二个字符串最少的步骤，如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;}

上一篇：生日蜡烛

下一篇：字符串循环右移