はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける最長部分増加列問題まとめ

最長部分増加列

  • LIS : Longest Increasing Subsequense
  • 参考サイト
  • 入れ子構造がLISに帰着できるケースはよくある(この問題は違うけど)
  • 二次元での入れ子構造は二次元平面上にプロットすると考えやすい 例1 例2
  • 一般に単調増加は狭義単調増加であるが、広義単調増加として解く問題もある

解説への手引き

AOJ 最長部分増加列

基本

ABC006 D. トランプ挿入ソート

LISやるだけだけど、気づくまでが問題

Codeforces #277 E. LIS of Sequence

LISをして、そっから色々やる
kmjpさんの解説

Codeforces #345 Div1. D. Zip-line

LISをして、そっから色々やる
kmjpさんの解説

「みんなのプロコン」 決勝 D. KthLIS

LISをして、そっから色々する
kmjpさんの解説

ABC038 D. プレゼント

入れ子構造系LIS

Typical DP Contest K. ターゲット

入れ子構造系LIS
kmjpさんの解説

CSAcademy Critical Cells

入れ子構造っぽいLIS
広義単調増加列のLIS

JOI春合宿2016 A. マトリョーシカ人形

入れ子構造ではあるが、難しい
神解説