UVA10192题解

为了尽可能满足父母亲的要求，我们应该取两个字符串的最长公共子序列。

洛谷模板题

设 \(dp_{i,j}\) 为 \(a\) 串匹配到第 \(i\) 位，\(b\) 串匹配到第 \(j\) 位时的最长公共子序列长度。

则易知 \(dp_{i,j}\) 可以由 \(dp_{i-1,j}\) 和 \(dp_{i,j-1}\) 转移过来。

如果 \(a_{i}=b_{j}\)，则 \(dp_{i,j}\) 还能从 \(dp_{i-1,j-1}\) 转移过来。

所以最终的柿子是：\(dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1},[a_i=b_j]\times dp_{i-1,j-1})\)。

其中，当 \(a_{i}=b_{j}\) 时，\([a_i=b_j]=1\)，否则 \([a_i=b_j]=0\)。

注意到字符串的长度很小，直接 \(O(n^2)\) 暴力转移即可。

#include<cstdio>
#include<cstring>
char a[110],b[110];
int n,m;
int dp[110][110];
int d;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	while(gets(a+1),gets(b+1))
	{
		if(a[1]=='#') break;
		d++;
		n=strlen(a+1),m=strlen(b+1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			}
		printf("Case #%d: you can visit at most %d cities.\n",d,dp[n][m]);
	}
	return 0;
}