2141545_pe.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>
# include <algorithm>
# define max(a,b) (a>b)?a:b

using namespace std;

long N;
int l1, l2;
char word1[50], word2[50];

void LCS()
{
	int m;
	int i, j;
	int dp[51][51];

	sort(word1,word1+l1);
	sort(word2,word2+l2);
	m = max(l1,l2);
	for(i = 0; i <= m; dp[i][0] = dp[0][i] = 0,i++);
	for(i = 1; i <= l1; i++)
		for(j = 1; j <= l2; j++)
			if(word1[i-1]==word2[j-1])
				dp[i][j] = dp[i-1][j-1]+1;
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
	printf("%d\n",l1+l2-2*dp[l1][l2]);
}

void input()
{
	long i;

	scanf("%ld",&N);
	getchar();
	for(i = 1; i <= N; i++)
	{
		printf("Case #%ld: ",i);
		gets(word1);gets(word2);
		l1 = strlen(word1);l2 = strlen(word2);
		if(l1==0||l2==0)
			printf("%d\n",l1+l2);
		else
			LCS();
	}
}

int main()
{
	input();
	return 1;
}