BZOJ 4993 [Usaco2017 Feb]Why Did the Cow Cross the Road II

发布于 2017-08-21  121 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4993

题意:

上下有两个长度为 n、位置对应的序列 A、B,
其中数的范围均为 1~n。若 abs(A[i]-B[j])<= 4,则 A[i] 与 B[j] 间可以连一条边。
现要求在边与边不相交的情况下的最大的连边数量 。 


直接套用 LCS 的\(n^2\)DP 即可。

 


一个非常弱的准退役OIER