# uva: 10066 – The Twin Towers ( LCS )

October 25, 2014 Leave a comment

Problem analysis:

- Given the descriptions of two dissimilar towers you are asked only to find out the number of tiles in the highest twin towers that can be built from them.
- 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.

Soltion analysis:

- LCS – solution of this problem is standard LCS algorithm

C++ solution:

#include<stdio.h> #define MAX 100 #define max(a,b) ((a)<(b) ? (b):(a)) int N1, N2; int firstT[MAX+1]; int secondT[MAX+1]; int c[MAX+1][MAX+1]; int lcsLength, nCase; int main10066() { int i,j; //int firstT[MAX]={0}; //int secondT[MAX]={0}; while(true) { scanf("%d %d", &N1, &N2); if(N1 ==0 && N2==0) break; for(i=1; i<=N1; i++) scanf("%d",&firstT[i]); for(i=1; i<=N2; i++) scanf("%d",&secondT[i]); /*for(i=0;i <=N1; i++) for(j=0;j<=N2; j++) c[i][j] = 0;*/ for(i=1; i<= N1; i++) for(j=1; j<= N2; j++) { if(firstT[i] == secondT[j]) { c[i][j] = c[i-1][j-1] + 1; } else { c[i][j] = max(c[i-1][j], c[i][j-1]); } } printf("Twin Towers #%d\n",++nCase); printf("Number of Tiles : %d\n\n",c[N1][N2]); } return 0; }

**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