为了尽可能满足父母亲的要求，我们应该取两个字符串的最长公共子序列。
设 \(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;
}