[UVa]10192:Vacation

LCS(Longest common subsequence)的問題。

[C](0.012)

	#include<stdio.h>
	#include<string.h>
	int main()
	{
	char s1[105], s2[105];
	int dataset = 1;
	while( gets(s1) && !( s1[0] == '#' && s1[1] == '\0' ) )
	{
	gets(s2);
	int LCS[105][105] = {0};
	int citynum1 = strlen(s1);
	int citynum2 = strlen(s2);
	int i, j;
	for( i = 1 ; i <= citynum1 ; i++ )
	for( j = 1 ; j <= citynum2 ; j++ )
	if( s1[i-1] == s2[j-1] )
	LCS[i][j] = LCS[i-1][j-1]+1;
	else
	LCS[i][j] = ( LCS[i-1][j] > LCS[i][j-1] )? LCS[i-1][j] : LCS[i][j-1];
	printf( "Case #%d: you can visit at most %d cities.\n", dataset++, LCS[citynum1][citynum2] );
	}
	return 0;
	}

view raw UVa10192.c hosted with ❤ by GitHub