UVA.10192 Vacation (DP LCS)

題意分析

某人要指定旅游路線，父母分別給出了一系列城市的旅游順序，求滿足父母建議的最大的城市數(shù)量是多少。

對(duì)于父母的建議分別作為2個(gè)子串，對(duì)其做LCS處理，最后的結(jié)果即為所求。

核心狀態(tài)轉(zhuǎn)移方程： 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]);

這里還有一個(gè)小技巧，當(dāng)希望讀取的字符數(shù)據(jù)，不是從字符數(shù)組的第0個(gè)元素開(kāi)始存放的時(shí)候，可以使用gets(str+n)這樣的讀取方式。其中n為某整數(shù)。因?yàn)間ets的參數(shù)是某字符串的起始地址。

代碼總覽