ex_2.cpp

问题描述 序列Z=<B

#include <iostream>
using namespace std;

int main()
{
	int N;
	int **c;
	char **b;
	char *x,*y;
	int i,j;
	int X,Y;		//个数
	int num_case=1;
	int count;
	cin>>N;
	while(num_case<=N)
	{
        count=0;
		cin>>X>>Y;
		c=new int *[X+1];
		b=new char *[X+1];
		for(i=0; i<=X ; i++)
		{
			c[i] = new int [Y+1];
			b[i] = new char [Y+1];
		}
		x=new char[X];
		y=new char[Y];
		for(i=0;i<X;i++)
			cin>>x[i];
		for(i=0;i<Y;i++)
			cin>>y[i];
		c[0][0]=0;
		for(i=1;i<=X;i++)
			c[i][0]=0;
		for(i=1;i<=Y;i++)
			c[0][i]=0;

		for(i=1;i<=X;i++)
			for(j=1;j<=Y;j++)
				if(x[i-1]==y[j-1])
				{
					c[i][j]=c[i-1][j-1]+1;
					b[i][j]='\\';
				}
				else if(c[i-1][j]>=c[i][j-1])
				{
					c[i][j]=c[i-1][j];
					b[i][j]='|';
				}
				else
				{
					c[i][j]=c[i][j-1];
					b[i][j]='-';
				}
		cout<<"Case "<<num_case<<endl;	
        i=X;j=Y;
		while(i!=0&&j!=0)
		{
			if(b[i][j]=='\\')
			{
				i--;
				j--;		
				count++;
			}
			else if(b[i][j]=='|')
				i--;
			else
				j--;
		}
		cout<<count<<endl;
		num_case++;
	}
	return 0;
}