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

最長部分増加列

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

問題

• 普通のLIS
  • AOJ 最長部分増加列
  • ABC006 D. トランプ挿入ソート
  • AGC024 Backfront 解説
  • ABC038 D. プレゼント
  • AGC019 Fountain Walk 解説
  • Typical DP Contest K. ターゲット
  • Codeforces #277 E. LIS of Sequence
  • Codeforces #345 Div1. D. Zip-line
  • 「みんなのプロコン」 決勝 D. KthLIS
  • CSAcademy Critical Cells
  • JOI春合宿2016 A. マトリョーシカ人形
  • yukicoder No.711 競技レーティング単調増加
  • ARC101 Robots and Exits （二次元）
  • EDPC Flowers 解説
  • AOJ LISum 解説
• 3次元LIS
  • AOJ Longest Chain 解説1 解説2
  • SRM747 Div1 Hard RochesterSequence https://www.hamayanhamayan.com/entry/2019/01/20/145544title=解説

以下、解説への手引き

解説への手引き