UC知道pascal编程问题高手进
来源：百度知道 编辑：UC知道 时间：2024/06/27 06:49:04
有两行自然数，UP[1..N]，DOWN[1..M]，如果UP[I]=DOWN[J]=K，那么上行的第I个位置的数就可以跟下行的第J个位置的数连一条线，称为一条K匹配，但是同一个位置的数最多只能连一条线。另外，每个K匹配都必须且至多跟一个L匹配相交且K≠L！现在要求一个最大的匹配数。
例如：以下两行数的最大匹配数为8
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3
输入格式：
从文件CROSS.DAT读入数据，第一行有两个正整数N和M。第二行N个UP的自然数，第三行M个DOWN的自然数。其中0<N、M<=200，UP、DOWN的数都不超过32767。
输出格式：
最大匹配数输出到CROSS.OUT。
例如：以下两行数的最大匹配数为8
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3
输入格式：
从文件CROSS.DAT读入数据，第一行有两个正整数N和M。第二行N个UP的自然数，第三行M个DOWN的自然数。其中0<N、M<=200，UP、DOWN的数都不超过32767。
输出格式：
最大匹配数输出到CROSS.OUT。
#include<iostream>
using namespace std;
int a[205]={0},b[205]={0},f[205][205]={0},n,m,la,lb;
int max(int x,int y)
{
return x>y?x:y;
}
void get(int i, int j)
{
int x=a[i],y=b[j];
la=i-1; lb=j-1;
while(a[la]!=y&&la>0)
la--;
while(b[lb]!=x&&lb>0)
lb--;
}
int main()
{
int i,j,t,tt;
cin>>tt;
for(t=1;t<=tt;t++)
{
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
cin>>b[i];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
get(i,j);
if(la!=0&&lb!=0&&a[la]!=b[lb])
{
if(f[la-1][lb-1]+2>f[i][j])