zp1425_p.cpp

来自「浙江大学acm在线判题器代码集。 本人在浙大acm判题器上的所有代码（心血） 」· C++ 代码 · 共 52 行

#include <iostream.h>
#define MAXNUM 1000

int x[MAXNUM], y[MAXNUM];
int table[MAXNUM][MAXNUM];
int nx, ny;

void Input()
{
	cin >> nx >> ny;
	int i;
	for (i = 1; i <= nx; ++i)
		cin >> x[i];
	for (i = 1; i <= ny; ++i)
		cin >> y[i];
}
void Matching()
{
	int i, j, m, n;
	for (i = 0; i <= nx; ++i)
		table[i][0] = table[i][1] = 0;
	for (j = 0; j <= ny; ++j)
		table[0][j] = table[1][j] = 0;
	for (i = 2; i <= nx; ++i)
		for (j = 2; j <= ny; ++j)
		{
			int maxnum = 0;
			maxnum = table[i-1][j]>table[i][j-1]?table[i-1][j]:table[i][j-1];
			for (m = i-1; m >0; --m)
				for (n = j-1; n >0; --n)
				{
					if(x[m] == y[j] && y[n] == x[i] && x[i] != y[j])
						if(maxnum < table[m-1][n-1] + 2)
							maxnum = table[m-1][n-1] + 2;
				}
			table[i][j] = maxnum;
		}
}

int main()
{
	int test;
	cin >> test;
	while(test--)
	{
		Input();
		Matching();
		cout << table[nx][ny] << endl;
	}
	return 0;
}