[AOJ] DPL 1 D 最長増加部分列

2020年9月27日

問題

方針

LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。

動的計画法と二分探索

参考を参照してください。

動的計画法とセグメント木

\( f_i \) を \( a_i \) の重複を許さない場合に何番目に大きいかという値とします。また、\( d(i) \) を \( i \) 番目に大きい値が末尾であるときの最長増加列の長さと定義します。

ここで、\( a_{0}\) から \( a_{i – 1} \) まで探索して \( d \) を構成し終えたとき、\( f_i \) について、

\[ d(f_i) < \max \left(d(0), d(1),\cdots, d(f_i – 1) \right) + 1\]

であるとき、

\[ d(f_i) \leftarrow \max \left(d(0), d(1),\cdots, d(f_i – 1) \right) + 1\]

と更新します。右辺の \( + 1 \) となっているのは、\( d(0)\) から \( d(f_i – 1) \) の末尾に \( a_i \) を追加し新しい最長増加列ができるためです。

コード

二分探索

セグメント木

参考