OJ Board

Code: Select all

#include <stdio.h>
#include <string.h>
char a[102],b[102];
int tbl[102][102];
int main()
{
    int i,j,na,cno=0,x,y,z,nb;
    while(scanf("%s%s",a,b)==2)
    {
	na=strlen(a);
	nb=strlen(b);
	for(i=0;i<na+1;i++)
	{
	    tbl[i][0]=0;
	}
	for(j=0;j<nb+1;j++)
	{
	    tbl[0][j]=0;
	}
	for(i=0;i<na;i++)
	    for(j=0;j<nb;j++)
	    {
		x=tbl[i+1][j];
		y=tbl[i][j+1];
		z=tbl[i][j]+1;
		if(a[i]==b[j])
		{
		    tbl[i+1][j+1]=z;
		}
		else
		{
		    tbl[i+1][j+1]=x>y?(x>z-1?x:z-1):(y>z-1?y:z-1);
		}
	    }
	printf("Case #%d: you can visit at most %d cities.\n",++cno,tbl[na][nb]);
    }
    return 0;
}

Code: Select all

# include<iostream>
# include<string>
# include<vector>
bool find_(vector<char> &A,int i,char s)
{
	for(int j = 0;j <= i;j++)
		if(A[j] == s)
			return true;
	return false;
}
int main()
{
  vector<char> A,B;
  char c;
  int count = 1;
  while(cin.get(c))
  {
	if(c == '#')
		break;
	while(c != '\n')
	{
		A.push_back(c);
		cin.get(c);
	}
	cin.get(c);
	while(c != '\n')
	{
		B.push_back(c);
		cin.get(c);
	}
	int **C = new int *[A.size()];
	int i,j;
	for(i = 0;i < A.size();i++)
	{
		C[i] = new int[B.size()];
		if (find_(A,i,B[0]))
			C[i][0] = 1;
		else
			C[i][0] = 0;
	}
	for(i = 0;i < B.size();i++)
		if(find_(B,i,A[0]))
			C[0][i] = 1;
		else
			C[0][i] = 0;
	for(i = 1;i < A.size();i++)
	{
		for(j = 1;j < B.size();j++)
		{
			if(A[i] == B[j])
				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];
		}
	}
	cout << "Case #" << count <<": you can visit atmost " << C[A.size() - 1][B.size() - 1] <<  " cities.\n";
	A.erase(A.begin(),A.end());
	B.erase(B.begin(),B.end());
	for(i = 0;i < A.size();i++)
		delete []C[i];
	delete []C;
	count++;
  }
  return 0;
}