坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑！！！！！！！！！
套着二分图外套的DP题！！！！
连续栽在这个类型的题上两次！！！！！！！！
一次是上次选拔赛的时候，那时候有两道题，一道是很明显的二分图，另一道稍微隐蔽一点，但是全都栽了，我以为，建了图我就是赢家，特么的根本建不出来！！！
上次就像写一篇来阐述一下某些二分图匹配的DP解法，无奈太懒了，结果今天就又栽在这里了……
题意：
给你一张二分图，要求点权相同的点才能相互匹配，而且每个匹配有且必须要有一个权值不同的匹配与其交叉，问最大匹配数量。
思路：
很容易想去匈牙利了有木有！！！但事实却是，dp求解。 思路如下：
假设我们要考虑的状态是第一行n位置，第二行m位置，且已知之前的所有最佳状态。考虑把，n，m交叉的匹配加入到匹配集合中。那么 如果两点的权值相同则不符合要求，否则，分别向前查找各自的匹配，再与这个状态之前的状态转移即可。
如果你还不懂，那你看一遍代码肯定能懂。
AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int a[maxn], b[maxn];
int dp[maxn][maxn];
int main()
{
int n, m, T;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
range(i, 1, n) scanf("%d", a + i);
range(i, 1, m) scanf("%d", b + i);
fill(dp, 0);
range(i, 2, n) range(j, 2, m)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (a[i] != b[j]) {
int k1 = i - 1, k2 = j - 1;
while (k1 && a[k1] != b[j])
k1--;
while (k2 && a[i] != b[k2])
k2--;
if (k1 && k2)
dp[i][j] = max(dp[i][j], dp[k1 - 1][k2 - 1] + 2);
}
}
printf("%d\n", dp[n][m]);
}
return 0;
}