题意：

          题目说了一大堆，其实就是求最长公共子序列。

解法：

         仿照《生物信息学》中的序列比对问题(感兴趣的话可以去了解了解)。

#include <iostream> #include <algorithm> #include <string> #include <cstring> using namespace std; int main() { string a, b; int DP[105][105], caseN = 0; while (getline(cin, a), a[0] != '#') { getline(cin, b); memset(DP, 0, sizeof(DP)); for (int i = 1; i <= a.size(); i++)for (int j = 1; j <= b.size(); j++) if (a[i-1] == b[j-1]) DP[i][j] += DP[i - 1][j - 1] + 1; else DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]); cout << "Case #" << ++caseN << ": you can visit at most " << DP[a.size()][b.size()] << " cities." << endl; } return 0; }