uva 10192 - Vacation 和 uva 10066 - The Twin Towers

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

解题思路：     根据最长公共子序列问题的性质，我们可以规定dp[i][j]为字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度, 由于下面涉及到i-1和j-1，那么这个时候我们一般从i=1和j=1开始到i<=len1, j<=len2。
                1ch1[i-1] = ch2[j-1] ,那么dp[i][j]= dp[i-1][j-1] + 1;
             2 ch1[i-1] != ch2[j-1] ,那么我们知道ch1[i]和ch2[j]不可能在同一个公共子序列里出现，那么这个时候的最长的子序列可能以ch1[i]或ch2[j]结尾，那么由于dp[i][j]= max {dp[i-1][j] , dp[i][j-1]}; 这个时候所有i=0或j=0的dp[i][j]= 0；
                            0 ; i = 0或j= 0;
就有          dp =   dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0 且ch1[i-1]= ch2[j-1];
                                dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};i > 0且j> 0且ch1[i-1]!= ch2[j-1];

10066代码：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 110

int N1 , N2;
int h1[MAXN] , h2[MAXN];
int dp[MAXN][MAXN];
int ans_max , cnt;

void solve(){
    int i , j;
    ans_max = 0;
    memset(dp , 0 , sizeof(dp));

    for(i = 1 ; i <= N1 ; i++){
        for(j = 1 ; j <= N2 ; j++){
            if(h1[i-1] == h2[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];
        }
    }
    printf("Number of Tiles : %d\n\n" , ans_max);
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    cnt = 1;
    while(scanf("%d%d" , &N1 , &N2)){
        if(N1 == 0 && N2 == 0) break;
        for(int i = 0 ; i < N1; i++) scanf("%d" , &h1[i]);
        for(int i = 0 ; i < N2; i++) scanf("%d" , &h2[i]);
        printf("Twin Towers #%d\n" , cnt++);
        solve();
    }
    return 0;
}
10192 代码：
[cpp]
/*
最长公共子序列解法
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 110

int 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;
}

作者：cgl1079743846

补充：软件开发 , C++ ,