いろいろなDPがありますが、これもまとめとくと良いと思ったので。
僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。
DPかメモ化再帰か――
ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするＤＰは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。
再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。
ではDP問の紹介。
(ネタバレ注意)
簡単な数え上げタイプ
・Kannondou[☆]
・A First Grader[★]
期待値とか
・Life game[★★]
・Ben Toh[★★☆]
最長増加部分列タイプ
( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )
・Russian dolls[★☆]
・SRM175 Div2 Hard Books(要ログイン)[★★☆]
ナップサックチックなやつ
・A Thief[★☆]
・At Boss’s Expense[★★]
・JOI2010-2011本選(問2)[★★★]
巡回セールスマンチックなやつ
・Patisserie[★★☆]
・Lupin The 4th[★★★☆]
状態数工夫して数え上げタイプ(直前のどこら辺まで必要な情報かとか)
・PKU 2663[★★☆]
・JOI Flag[★★★★]
・CF#79(D) Caesar’s Legions[★★☆]
・SRM501 D1M(要ログイン)[★★★☆]
BITとか累積和を使うと良い数え上げ
・Bingo[★★★★]
・SRM501 D1M(要ログイン) ←さっきのやつのO(NM^3)とか[★★★★★]
・CF#79(Div1 B) Buses[★★★☆]
・SRM520 D1M(要ログイン)[★★★★☆]
状態数を特に工夫する必要があるやつ
・KULASIS[★★★☆]
・Dividing Snacks[★★★☆]
その他おすすめ
・Baby Tree[★★]
・Icicles[★★☆]
・本棚(2011年度JOI春合宿[★★★★★] (部分点解法(30%)なら[★★★]くらい)
