UVA.10192 Vacation (DP LCS)

2019-11-08 19:45:33

字体：大中小

来源：转载

供稿：网友

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 105using 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;}

上一篇：UVA.357 Let Me Count The Ways (DP 完全背包)

下一篇：121. Best Time to Buy and Sell Stock