3065 交叉匹配

Task
给定两行数，求这两行数的最大交叉匹配数。
交叉匹配的原则：
① 上下两行，只有值相同的才能连线匹配。
② 任意一条a匹配线有且仅有一条b匹配线和它相交，且a，b数值不同。
左边是合法的，而右边是不合法的。

N<=2000

Solution
观察到，如果a，b上下相交，那么两个红色箭头范围内的不可能再有匹配线，否则就不满足②条件。那么一対匹配会把区间分割出独立的一段，类似于前n个的m划分。

根据”上下两行匹配”,联想到字符串的编辑距离，那么是否可以用dp去做呢?

如果令dp[ i ][ j ]表示第1行前i个，第2行前j个最大匹配数。
因为表示的是前缀信息，当前没有匹配的话，是从dp ( i-1 , j )或dp ( i , j-1 )选一个最大的转移。那么dp值一定是随i，j的递增而不递减的。
当前有匹配的话，一定是用第1行的i与第2行的j去交叉匹配。

例如，假如出现下图的情况

用同颜色表示一対互相匹配线段。
有人觉得，如果不从i，j转移而是从i，j前面的蓝色部分转移，不是比红色的更优吗？
但是因为蓝色部分已经包括在前缀信息里了，所以即使你找到最优的蓝色部分，也只是重复操作。

const int M=2005;
int dp[M][M],len[3],A[3][M],pos[3][M<<1],B[M<<1];//401w

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！