最少步

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 22 Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

有两个等长字符串str1和str2,仅由字符A和B组成, 现在要把str1变换成str2,唯一允许的变换操作是把str1的某个连续区间全变成A或者全变成B. 问怎样变换才能步数最少

Input

第一行是一个整数t (t ≤ 100),表示测试用例的数目.每一测试用例有两行组成,第一行是str1,第二行是str2,字符串长度不大于200,字符串前导和后缀均无空白符.

Output

对于每一测试用例,输出最小空白符.

Sample Input

2BBAABAAABABBAA

Sample Output

12 #include
   
    #include
    
     #include
     
      #define MAXN 205int dp[MAXN][MAXN];int rem[MAXN][MAXN],remA[MAXN][MAXN],remB[MAXN][MAXN];char s1[MAXN],s2[MAXN];int inite(int len){	int i,j,k,temp;	memset(rem, 0, sizeof(rem));	memset(remA, 0, sizeof(remA));	memset(remB, 0, sizeof(remB));	for(i = 0; i < len; i++)	{		for(j = i; j < len; j++)		{			temp = 0;			if(j)temp = rem[i][j-1];			if(s1[j]!=s2[j])				rem[i][j]=temp + 1;			else				rem[i][j]=temp;			for(k = i; k <= j; k++)			{				if(s2[k]!=s2[k+1]||(k+1>j))				{					if(s2[k]=='A')						remB[i][j]++;					else						remA[i][j]++;				}			}		}	}	for(i = j = 0;j < len;j++)	{		if((s1[j]!=s1[j+1])||j+1>=len)		{			if(s1[j-1]=='A')				remA[i][j-1]-=1;			else				remB[i][j-1]-=1;			i = j + 1;		}	}	return 0;}int DP(int l,int r){	int i,temp;	if(dp[l][r]!=-1)return dp[l][r];	dp[l][r]=(rem[l][r]<(temp=(remA[l][r]+1)))?rem[l][r]:temp;	dp[l][r]=(dp[l][r]<(temp=(remB[l][r]+1)))?dp[l][r]:temp;	for(i = l; i < r; i++)	{		temp = DP(l,i)+DP(i+1,r);		if(temp

转载地址：http://zeuvi.baihongyu.com/

你可能感兴趣的文章