UVa 10192 Vacation (DP&LCS)

10192 - Vacation

Time limit: 3.000 seconds 

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1133

水。

完整代码：

/*0.019s*/

#include<bits/stdc++.h>
using namespace std;

char a[105], b[105];
int dp[105][105];

int main()
{
	int lena, lenb, i, j, cas = 0;
	while (gets(a), a[0] != '#')
	{
		gets(b);
		lena = strlen(a), lenb = strlen(b);
		memset(dp, 0, sizeof(dp));
		for (i = 0; i < lena; ++i)
			for (j = 0; j < lenb; ++j)
			{
				if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
				else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		printf("Case #%d: you can visit at most %d cities.\n", ++cas, dp[lena][lenb]);
	}
	return 0;
}