1692.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
int links[101][101];
int f[101],s[101],n,m;
int answer;

void find()
{int i,j,t,k,h;
	links[0][0]=0;
	links[0][1]=0;
	links[1][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{t=links[i-1][j]>links[i][j-1]?links[i-1][j]:links[i][j-1];
 if(f[i]!=s[j])
 {
 for(k=i-1;k>=1;k--)
	 if(f[k]==s[j])break;
 for(h=j-1;h>=1;h--)
	 if(f[i]==s[h])break;
 if(k&&h&&links[k-1][h-1]+1>t)t=links[k-1][h-1]+1;
 }
 links[i][j]=t;
}
}


int main()
{int i,t;
	cin>>t;
	while(t--)
	{cin>>n>>m;
		for(i=1;i<=n;i++)cin>>f[i];
		for(i=1;i<=m;i++)cin>>s[i];
		find();
		cout<<links[n][m]*2<<endl;
	}
return 0;
}