uva 10192 Vacation（动态规划：LCS）

本文主要是介绍uva 10192 Vacation（动态规划：LCS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

水题，但是有个坑

输入的字符串中可能含空格字符

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 110
using namespace std;int dp[MAXN][MAXN];
char str1[MAXN], str2[MAXN];int main(void) {int t = 1;while(cin.getline(str1, 105) && str1[0] != '#') {cin.getline(str2, 105);memset(dp, 0, sizeof(dp));int len1 = strlen(str1);int len2 = strlen(str2);for(int i=0; i<len1; ++i) {for(int j=0; j<len2; ++j) {if(str1[i] == str2[j]) {dp[i+1][j+1] = max(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", t++, dp[len1][len2]);}return 0;
}

这篇关于uva 10192 Vacation（动态规划：LCS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---