3636411_ac_94ms_220k.c

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

#include <stdio.h>
#include <string.h>

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

int f(int a)
{
	if (a % 2 == 1)
		a--;
	return a;
}

int a[100], b[100];
int n1, n2;

int maxPossibleMatch(int sta, int stb)
{
	return f(min(n1 - sta, n2 - stb));
}

int MAX[100][100];

int maxMatch(int sta, int stb)
{
	int max = 0;
	int i, j, k, l, tmp;

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

int main()
{
	int cas, i;

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