1692 Crossed Matchings

問題概要

二列に整数が並んでいる。上の列と下の列の同じ数字を線で結ぶことができる。
このとき、次のようなマッチングの数を最大にしたい。

• 一つの数字からは最大一つの直線しかひかれていない
• 全ての直線は、異なる数字同士を結ぶ直線と一度だけ交わっている

最大マッチングの数を求めよ。列の数はそれぞれ100以下である。

解法

dp[i][j]に、上の列i個目まで、下の列j個目までを使ったときにできる最大のマッチングの数をもつ。
A-B,C-Dのようなマッチングがあるとき、dp[B][D]=max(dp[B][D],dp[A-1][C-1]+2)であるので、テーブルを更新できる。

ソースコード

int n,m,a[100],b[100];
int dp[101][101];

int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		scanf("%d%d",&n,&m);
		rep(i,n)scanf("%d",a+i);
		rep(i,m)scanf("%d",b+i);
		rep(i,n+1)rep(j,n+1)dp[i][j]=0;
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j]);
				dp[i][j]=max(dp[i][j],dp[i][j-1]);
			}
			rep(j,m)if(a[i-1]==b[j])
			for(int k=j+1;k<m;k++)if(b[k]!=b[j])
			rep(l,i)if(a[l]==b[k])
			dp[i][k+1]=max(dp[i][k+1],dp[l][j]+2);
		}
		printf("%d\n",dp[n][m]);
	}
	return 0;
}