UVa 10192 Vacation：DP&LCS

UVa 10192 Vacation：DP&LCS2014-07-28 csdn博客 synapse7

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.
", ++cas, dp[lena][lenb]）;}return 0;}