3636302_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int min(int a, int b)
{
	return a < b ? a : b;
}

int maxPossibleMatch(int a[], int b[])
{
	int i, j;

	for (i = 0; a[i] != 0; i++);
	for (j = 0; b[j] != 0; j++);
	return min(i, j) / 2;
}

int maxMatch(int a[], int b[])
{
	int max = 0;
	int i, j, k, l, tmp, s, t;

	for (i = 0; a[i] != 0; i++)
	{
		for (j = 0; b[j] != 0; j++)
		{
			if (a[i] == b[j])
			{
				tmp = 0;
				for (k = i + 1; a[k] != 0 && tmp == 0; k++)
				{
					for (l = 0; l < j; l++)
					{
						if (a[k] == b[l] && a[k] != a[i])
						{
							s = k;
							t = j;
							tmp = 2;
							break;
						}
					}
				}
				if (tmp == 2)
				{
					if (tmp + maxPossibleMatch(&a[s + 1], &b[t + 1]) <= max)
					{
						continue;
					}
					tmp += maxMatch(&a[s + 1], &b[t + 1]);
					if (tmp > max)
					{
						max = tmp;
					}
				}
			}
		}
	}
	return max;
}

int main()
{
	int a[100], b[100];
	int n1, n2;
	int cas, i;

	scanf("%d", &cas);
	while (cas-- > 0)
	{
		scanf("%d%d", &n1, &n2);
		for (i = 0; i < n1; i++)
		{
			scanf("%d", &a[i]);
		}
		a[n1] = 0;
		for (i = 0; i < n2; i++)
		{
			scanf("%d", &b[i]);
		}
		b[n2] = 0;
		printf("%d\n", maxMatch(a, b));
	}
	return 0;
}