N(i, j)的最大不相交子集为 MNS(i,j)。...Size(i,j) = |MNS(i,j)|(最大不相交子集线路的条数)
- N(i,j): 上端接线柱从1到i,下端接线柱从1到j,在这个范围内的接线情况。...当 j ≥ Π(i), (i,Π(i)) ∈ MNS(即要这根线)(i,j)。 对于任意 (t,Π(t)) ∈ MNS(i,j) 有 t < i 且 Π(t) < Π(i)。...这种情况下,MNS(i,j) - {(i,Π(i))}是N(i-1, Π(i)-1) 的最大不相交子集。
3....若 (i,Π(i)) ∉ N(i,j)(即不要这根线), 则对任意 (t,Π(t)) ∈ MNS(i,j) 有 t < i。 从而 MNS(i,j) ∈ N(i-1,j)。