uva 10192 - Vacation 和 uva 10066 - The Twin Towers

点击打开链接uva 10066

点击打开链接uva 10192

题目意思 ： 求最长公共子序列

解题思路： 根据最长公共子序列问题的性质，我们可以规定dp[i][j]为字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度, 由于下面涉及到i-1和j-1，那么这个时候我们一般从i=1和j=1开始到i<=len1, j<=len2。

/*最长公共子序列解法*/#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <stack>#include <queue>#include <cmath>using namespace std;#define MAXN 110int dp[MAXN][MAXN];char ch1[MAXN] , ch2[MAXN];int cnt , ans_max;void solve(){ int i , j; memset(dp , 0 , sizeof(dp)); ans_max = 0 ; for(i = 1 ; i <= strlen(ch1) ; i++){ for(j = 1 ; j <= strlen(ch2) ; j++){ if(ch1[i-1] == ch2[j-1]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]; if(ans_max < dp[i][j]) ans_max = dp[i][j]; } } }int main(){ //freopen("input.txt" , "r" , stdin); cnt = 1; while(gets(ch1)){ if(strcmp(ch1 , "#") == 0) break; gets(ch2); solve(); printf("Case #%d: you can visit at most %d cities.\n" , cnt++ , ans_max); } return 0;}

1楼dxxang昨天 09:25

学习