#include<iostream>
using namespace std;
using namespace std;
const int maxn = 510;
int num1[maxn],num2[maxn];
int n1,n2;
void GCIS()
{
	int i,j;
	int lef[maxn];
	for(i=0;i<n2;i++)
		lef[i]=-2;
	int length[maxn]={0};
	int temp;
	int t,l;
	for(i=0;i<n1;i++)
	{
		temp=num1[i];
		t=1;
		l=-1;
		for(j=0;j<n2;j++)
		{
			if(length[j]&&num1[i]>num2[j])
			{
				if(t==length[j])
				{
					t++;
				}
			}
			else if(num1[i]==num2[j]&&t>length[j])
			{
				length[j]=t;
				lef[j]=i;
			}
			else
				;
		}
	}
	
	int m=0;
	for(i=0;i<n2;i++)
	{
		if(length[i]>=m)
		{
			m=length[i];
			t=i;
		}
	}
	printf("%d\n",m);
	if(m==0)
	{
		return;
	}
	int aa[maxn];
	j=1;
	aa[0]=num2[t];
	m--;
	while(m>0)
	{
		for(i=0;i<n2;i++)
		{
			if(length[i]==m&&lef[i]<lef[t]&&num2[i]<num2[t])
			{
				aa[j++]=num2[i];
				t=i;
				break;
			}
		}
		m--;
	}
	j--;
	while(j>=0)
	{
		printf("%d ",aa[j--]);
	}

	printf("\n");
}

int main(void)
{
	int i;
	while(scanf("%d",&n1)==1)
	{
	for(i=0;i<n1;i++)
		scanf("%d",&num1[i]);
	scanf("%d",&n2);
	for(i=0;i<n2;i++)
		scanf("%d",&num2[i]);
	GCIS();
	}
	return 0;
}

• Re:谁能帮忙看看吗？效率n^2可是一直WA (17) DreamOfGame 2008-11-06 22:43:09