最長増加部分列

ある数列 A = {a1, a2, ... an} があるとき B = {ai, ai+1, ...ak } (1 <= i < k <= n) を部分列と呼ぶ。そして ai < ai+1 を満たすときBは増加部分列と呼ぶ。増加部分列のうち最長のものを見つけたい。

cross-free matching

線分がM個ある

(a1, 0), (b1, 1) (ai, 0), (bi, 1) (am, 0), (bm, 1)

このとき、線分が交差しないように選択するということは bi < bi+1 を満たすということこれは LIS に帰着できる

LIS に帰着するため2つの線分の関係を下記のように定義する。

(ai, 0), (bi, 1) < (aj, 0), (bj, 1) は

ai < aj であるそうでないならば ai = aj かつ bi > bj である

つまり (10, 0), (11, 1) < (10, 0), (10, 1)

である。

この条件のもとで線分が < 関係を満たすように並べ替えれば線分交差は LIS に帰着できる…らしい

動的計画法を用いる。 dp[i][x] は i 項目まで計算対象としたとき、末尾が x である場合のLISの最大長とする。