UVA.10192 Vacation (DP LCS)

题意分析

某人要指定旅游路线，父母分别给出了一系列城市的旅游顺序，求满足父母建议的最大的城市数量是多少。

对于父母的建议分别作为2个子串，对其做LCS处理，最后的结果即为所求。

核心状态转移方程：

if(c1[i] == c2[j]) dp[i][j] =dp[i-1][j-1]+1;

else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

这里还有一个小技巧，当希望读取的字符数据，不是从字符数组的第0个元素开始存放的时候，可以使用gets(str+n)这样的读取方式。其中n为某整数。因为gets的参数是某字符串的起始地址。

代码总览

/*

    Title:UVA.10192

    Author:pengwill

    Date:2017-2-16

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 105

using namespace std;

char c1[nmax],c2[nmax];

int dp[nmax][nmax];

int main()

{

    int cas = 0;

    while(gets(c1+1),gets(c2+1)){

        if(c1[1]=='#') break;

        memset(dp,0,sizeof(dp));

        int len1 = strlen(c1+1),len2 = strlen(c2+1);

        for(int i =1; i<=len1;++i){

            for(int j = 1; j<=len2;++j){

               if(c1[i] == c2[j]) dp[i][j] =dp[i-1][j-1]+1;

               else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

            }

        }

        printf("Case #%d: you can visit at most %d cities.\n",++cas,dp[len1][len2]);

    }

    return 0;

}