http://poj.org/problem?id=1692
题意:两个集合分别有N1、N2个元素,求最大匹配交叉对的数目。(匹配交叉对:a和b中有两个元素相等,称其为value-match;现在是要有两个va-match,vb-match,并且他们相交,va!=vb)
Idea:
类似LCS;
f[i] = MAX{f[i-1][j-1],f[i][j-1],f[i-1][j] }
f[i] = MAX{f[i][j],f[m-1][n-1]+1}
(m = preA[i-1][b[j]];n =preB[j-1][a[i]];m != 0 & n != 0& a[i] != b[j])
然后pre怎么算呢?
直接枚举pre的两维然后再确定值,N^3;
观察下,发现其实也有递推关系的。
#include <cstdio> #include <iostream> #include <fstream> #include <cstring> using namespace std; #define MAX(x,y) ((x)>(y)?(x):(y)) #define MIN(x,y) ((x)<(y)?(x):(y)) int a[109],b[109]; void calpre(int n,int pre[109][109],int t[109]) { memset(pre,sizeof(pre)); for (int i = 1;i <= n;i++) { for (int j = 1;j <= 100;j++) { pre[i][j] = pre[i-1][j]; } pre[i][t[i]] = i;//pre[i][a[i]] = i; 。。。 } } int main() { freopen("test.txt","r",stdin); int M,N1,N2; scanf("%d",&M); while(M--) { scanf("%d%d",&N1,&N2); for (int i = 1;i <= N1;i++) scanf("%d",&a[i]); for (int i = 1;i <= N2;i++) scanf("%d",&b[i]); static int preA[109][109],preB[109][109]; calpre(N1,preA,a); calpre(N2,preB,b); static int f[109][109]; int m,n; memset(f,sizeof(f)); for (int i = 1;i <= N1;i++) { for (int j = 1;j <= N2;j++) { f[i][j] = MAX(f[i-1][j-1],f[i-1][j]); f[i][j] = MAX(f[i][j],f[i][j-1]); m = preA[i-1][b[j]]; n = preB[j-1][a[i]]; if (m && n && a[i] != b[j])//if (m+n && a[i] != b[j]) 把有一个为0写成了同时为0 { f[i][j] = MAX(f[i][j],f[m-1][n-1] + 1);//f[i][j] = MAX(f[i][j],f[m][n]+1); m、n都应该减1的 } } } printf("%d\n",f[N1][N2]*2); } return 0; } /* 1st:WA!方法是对,但是有几个地方写挫了。(1个地方是数学表达,1个代码表达,思路还是不够严密) 2nd:AC! */