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

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

hamayanhamayan's blog

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

競技プログラミング

入門: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021246
基礎: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021329

桁DP

dp[i][j][k] := i桁目までである条件jで、境界上にあるかの真偽kの何か

高難易度区間DP

桁DP

Typical DP Contest E. 数

http://tdpc.contest.atcoder.jp/tasks/tdpc_number
dp[i][j][k] := i桁目まで確定していて各桁の和modDがjで境界線上にあればk=1,なければk=0

高難易度区間DP

ABC 008 D. 金塊ゲーム

http://abc008.contest.atcoder.jp/tasks/abc008_4
dp[sx][sy][tx][ty] := 左上(sx,sy)右下(tx,ty)の時に取れる金塊の最大値
99点解法ではこれで良いが、100点を取るには更に座圧する必要がある