読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

競技プログラミングにおける基礎動的計画法問題まとめ

入門: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021246
応用: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021423

木DP

木の頂点についてDPを作る
dp[i] := 頂点iの部分木についての何か

bitDP

選択済みの集合に対してのDPを作る
dp[state] := 選択済みの集合stateについての何か
条件がN <= 16くらいという制約がある。dp[1<<16]と定義する。

yukicoder No.357 品物の並び替え (Middle)

http://yukicoder.me/problems/no/357

yukicoder No.286 Modulo Discount Store

http://yukicoder.me/problems/no/286

yukicoder No.107 モンスター

http://yukicoder.me/problems/no/107

yukicoder No.134 走れ!サブロー君

http://yukicoder.me/problems/no/134

CodeChef Bear and Shop Trip

https://www.codechef.com/problems/SHOPTRIP

発展yes/no

Kickstart Round A 2017 B. Patterns Overlap

https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p1











以下、短い解説。

木DP

ABC 036 D. 塗り絵

http://abc036.contest.atcoder.jp/tasks/abc036_d
dp[i][j] := 頂点i以下が塗られていて、頂点iがj=0なら黒,j=1なら白に塗られている組合せ

bitDP

yukicoder No.357 品物の並び替え (Middle)

http://yukicoder.me/problems/no/357
dp[state] := stateの商品がもう並べられている時の得点の合計
http://yukicoder.me/submissions/153479

yukicoder No.286 Modulo Discount Store

http://yukicoder.me/problems/no/286
dp[state] := stateの商品を買ったときの購入金額の合計の最小値
上の問題とほぼ同じ
http://yukicoder.me/submissions/153481

yukicoder No.107 モンスター

http://yukicoder.me/problems/no/107
dp[state] := stateの敵を倒した時の体力の最大値
http://yukicoder.me/submissions/153489

yukicoder No.134 走れ!サブロー君

http://yukicoder.me/problems/no/134
dp[state][last] := stateの商品を配達済みで最後にlastの場所に配達した場合の時間の最小値
http://yukicoder.me/submissions/153501

CodeChef Bear and Shop Trip

https://www.codechef.com/viewsolution/13382723
dp[state][last] := stateの材料を集めて最後に店lastにいる時の累計移動距離の最小値

発展yes/no

Kickstart Round A 2017 B. Patterns Overlap

https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p1
dp[i][ii][j][jj] = 1番目の文字列のi番目までで文字列の*をii個使用、2番目の文字列のj番目までで文字列の*をjj個使用となる組合せが存在するか