2011-05-29 22:34:07Morris
a133. 10066 - The Twin Towers
http://zerojudge.tw/ShowProblem?problemid=a133
內容 ：
很久以前在一個古老師王國有兩座形狀不同的塔聳立在兩個不同的城市裡。塔是以圓形磁磚疊起來的。每塊磁磚的高度相同且半徑均為整數。因此，儘管兩座塔形狀不同，卻包含了許多相同的磁磚。
然而在建塔的一千多年後，國王命令建築師移除某些磁磚好使兩座塔的形狀大小都相同，並且要維持可能的最大高度。磁磚的順序須與原始建築相同。國王認為這樣可以象徵兩個城市的和諧與平等。他名之為「雙子星塔」。
現在，大約兩千年後，你被賦予一個更簡單的任務：給你兩座塔的描述，你只要找出可能的最大磁磚數。
輸入說明
：
輸入有若干筆測資。每筆測資代表一對雙子星塔。
每筆測資的第一行有兩個整數 N1 及 N2 (1 <= N1, N2 <= 100) 代表兩座塔的磁磚數。下一行含有 N1 個正整數，代表第一座塔由上而下磁磚的半徑。下一行的 N2 個整數則是第二座塔由上而下磁磚的半徑。
N1 及 N2 為 0 代表輸入結束。
輸出說明
：
對於每一對雙子星塔，輸出它的編號及每座塔所能保留的最大可能磁磚數。測資間請空一行。
範例輸入 ：
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
提示
：
出處
：
/**********************************************************************************/
/* Problem: a133 "10066 - The Twin Towers" from UVa ACM 10066 */
/* Language: C */
/* Result: AC (74ms, 308KB) on ZeroJudge */
/* Author: morris1028 at 2011-05-29 21:22:49 */
/**********************************************************************************/
#include<stdio.h>
main() {
int N1, N2, a, b, s1[102], s2[102], C = 0;
while(scanf("%d %d", &N1, &N2) == 2) {
if(N1 + N2 == 0) break;
for(a = 1; a <= N1; a++)
scanf("%d", &s1[a]);
for(a = 1; a <= N2; a++)
scanf("%d", &s2[a]);
int LCS[102][102] = {};
for(a = 1; a <= N1; a++)
for(b = 1; b <=N2; b++)
if(s1[a] == s2[b])
LCS[a][b] = LCS[a-1][b-1] + 1;
else
LCS[a][b] = (LCS[a-1][b] > LCS[a][b-1])? LCS[a-1][b] : LCS[a][b-1];
printf("Twin Towers #%d\n", ++C);
printf("Number of Tiles : %d\n\n", LCS[N1][N2]);
}
return 0;
}