ZJU/ZOJ 1425 Crossed Matchings 解题报告

题目大意是给出两行数，第一行上的数和第二行上相同的数连接算一个匹配，一个匹配成立当且仅当它和另一个不同的数的匹配交叉且仅能有一个交叉，且一个数不能与多个数匹配。求给出的两行数最多可以有多少个有效匹配。

这又是一个经典的最优匹配数DP模型，方程的推导思想和ZJU/ZOJ 1027类似，不过本题多了一个条件限制，要求一个数不能匹配多个数且要求匹配交叉才算有效匹配。因此我们可以做一个预处理，用一个记录每一行中某个位置前出现过的所有数字的离它最近的位置，则可以推导出状态转移方程是f[i,j]=max(f[i-1,j],f[i,j-1],f[pos1[i,num2[j]]-1,pos2[j,num1[i]]-1]+2)(2<=i<=n1,2<=j<=n2);其中f[i,j]表示用第一行的前i个数字和第二行的前j个数字匹配所能得到的最大有效匹配数，pos1[i,num2[j]]表示距离第一行第i个数最近的第二行第j个数的位置，pos2[j,num1[i]]表示距离第二行第j个数最近的第一行第i个数的位置。f[pos1[i,num2[j]]-1,pos2[j,num1[i]]-1]+2有效的前提是num1[i]<>num2[j]且pos1[i,num2[j]]>0和pos2[j,num1[i]]>0。

3004961 2008-07-25 18:44:54 Accepted 1425 FPC 00:00.00 432K IwfWcf@LZOI