UVA-10066 - The Twin Towers

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20161220 大學程式能力檢定 CPE」題目。
• 相同題目：ZOJ-a133 / NCTU-10630

題意概要

題目給定兩組序列的長度，並給定這兩組序列的個別數字，請求出者兩個序列的最長共同子序列 (Longest Common Subsequence; LCS) 的長度。

• 分析：本題為動態規劃 (Dynamic Programming; DP) 的「最常共同子序列 (Longest Common Subsequence; LCS)」題目，題目給定兩組序列的長度，並給定這兩組序列的個別數字，由動態規劃的方式求解即可。

Input

The input file consists of several data blocks. Each data block describes a pair of towers. The first line of a data block contains two integers $N_1$ and $N_2$ ($1 \le N_1, N_2 \le 100$) indicating the number of tiles respectively in the two towers. The next line contains $N_1$ positive integers giving the radii of the tiles (from top to bottom) in the first tower. Then follows another line containing $N_2$ integers giving the radii of the tiles (from top to bottom) in the second tower. The input file terminates with two zeros for $N_1$ and $N_2$.

Output

For each pair of towers in the input first output the twin tower number followed by the number of tiles (in one tower) in the highest possible twin towers that can be built from them. Print a blank line after the output of each data set.

Sample Input

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

Sample Output

Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6