主題

ZeroJudge - a133: 10066 - The Twin Towers 解題心得

Not In My Back Yard | 2021-01-19 00:00:03

題目連結:


題目大意:
輸入有多筆測試資料。測資第一列給定兩正整數 N1 、 N2 (1 ≦ N1 、 N2 ≦ 100),代表兩座塔分別有的磁磚數。接著的一列給定 N1 個正整數,代表第一座塔每個磁磚的半徑、再接著一列給定 N2 個正整數,代表第二座塔每一個磁磚的半徑。

現在兩座塔各自要移除一部分磁磚(不更動原本磁磚之間的順序)使得兩座塔的磁磚完全一致(半徑一樣),試問這兩座塔最多能保留多少磁磚?



範例輸入:
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0


範例輸出:
Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6


解題思維:
本題即是求兩個數列的最長共同子序列(Longest Common Subsequence,LCS),作法可以參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
26 巴幣: 0

創作回應

更多創作