ACM (UVa) : 10066


#include <iostream>
#include <cstring>
using namespace std;

int c [110] [110] = {0}; // global
int n1, n2;

int lcs_length (int x [], int y [])
{
	int length_x = n1;
	int length_y = n2;
	int i, j;

	for (i = 1; i <= length_x; i++)
		c [i] [0] = 0;
	for (j = 0; j <= length_y; j++)
		c [0] [j] = 0;

	for (i = 1; i <= length_x; i++) {
		for (j = 1; j <= length_y; j++) {
			if (x [i - 1] == y [j - 1]) 
				c [i] [j] = c [i - 1] [j - 1] + 1;
			else if (c [i - 1] [j] >= c [i] [j - 1]) 
				c [i] [j] = c [i - 1] [j];
			else 
				c [i] [j] = c [i] [j - 1];
		}
	}
	return c [length_x] [length_y];
}

int main ()
{
	int first [110], second [110];
	int count = 0, i;
	
	while (cin >> n1 >> n2 && n1 && n2) {
		
		for ( i = 0; i < n1; i++ )
			cin >> first [i];
		for ( i = 0; i < n2; i++ )
			cin >> second [i];

		cout << "Twin Towers #" << ++count << endl;
		cout << "Number of Tiles : " << lcs_length (first, second) << "\n" << endl;
		
	}

	return 0;
}

2 thoughts on “ACM (UVa) : 10066

  1. Could You tell me what is wrong with my code…………..
    Thanks in advance…………

    #include
    #include
    #include
    using namespace std;
    int main()
    {
    int n1,n2,i,j,n=1;
    while(cin>>n1>>n2)
    {
    int arr1[n1];
    int arr2[n2];
    int arr3[n1+1][n2+1];
    for(i=0;i<n1;++i)
    scanf("%d",&arr1[i]);
    for(i=0;i<n2;++i)
    scanf("%d",&arr2[i]);
    for(i=0;i<=n1;++i)
    {
    for(j=0;j<=n2;++j)
    arr3[i][j]=0;
    }
    for(i=1;i<=n1;++i)
    {
    for(j=1;j<=n2;++j)
    {
    if(arr1[i-1]==arr2[j-1])
    arr3[i][j]=arr3[i-1][j-1]+1;
    else
    arr3[i][j]=max(arr3[i-1][j],arr3[i][j-1]);
    }
    }
    cout<<"Twin Towers #"<<n<<endl;
    cout<<"Number of Tiles : "<<arr3[n1][n2]<<endl;
    cout<<endl;
    ++n;
    }
    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s