a133. 10066 - The Twin Towers
標籤 : DP LCS 最長共同子序列
通過比率 : 1125人/1215人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-05-25 18:03

內容

很久以前在一個古老師王國有兩座形狀不同的塔聳立在兩個不同的城市裡。塔是以圓形磁磚疊起來的。每塊磁磚的高度相同且半徑均為整數。因此,儘管兩座塔形狀不同,卻包含了許多相同的磁磚。

然而在建塔的一千多年後,國王命令建築師移除某些磁磚好使兩座塔的形狀大小都相同,並且要維持可能的最大高度。磁磚的順序須與原始建築相同。國王認為這樣可以象徵兩個城市的和諧與平等。他名之為「雙子星塔」。

現在,大約兩千年後,你被賦予一個更簡單的任務:給你兩座塔的描述,你只要找出可能的最大磁磚數。

輸入說明

輸入有若干筆測資。每筆測資代表一對雙子星塔。

每筆測資的第一行有兩個整數 N1 及 N2 (1 <= N1, N2 <= 100) 代表兩座塔的磁磚數。下一行含有 N1 個正整數,代表第一座塔由上而下磁磚的半徑。下一行的 N2 個整數則是第二座塔由上而下磁磚的半徑。

N1 及 N2 為 0 代表輸入結束。

輸出說明
對於每一對雙子星塔,輸出它的編號及每座塔所能保留的最大可能磁磚數。測資間請空一行。
範例輸入 #1
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
範例輸出 #1
Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
標籤:
DP LCS 最長共同子序列
出處:
UVa10066 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
36992 liaoweichen1 ... (M_SQRT) a133
273 2023-08-19 07:59
39443 webinteng@gm ... (鄧均淮(小壞)) a133
LCS
70 2024-02-22 10:05
31934 kevin030162 (凱文) a133
The Twin Towers
581 2022-08-29 18:00
26969 alison.acorn ... (aa w) a133
Pure LCS
1347 2021-09-05 10:04
13981 yungshenglu1 ... (David Lu) a133
The Twin Towers
2643 2018-05-24 18:14