区間に対してのDPを区間DPと一般的に言う。類題と主なやり方をここに書く。
更新のやり方
区間DPは、区間に対するようなDPなので、普通のように漸化式を立てても前から回すことはできない。実装で楽なのは、メモ化再帰である。
しかし、メモ化再帰でMLEするような意地悪な問題もあるため、普通のような漸化式で解かざるを得ないものもある。forループをぶん回して解く際には、区間が小さい方から順に計算する。
しかし、メモ化再帰でMLEするような意地悪な問題もあるため、普通のような漸化式で解かざるを得ないものもある。forループをぶん回して解く際には、区間が小さい方から順に計算する。
類題にテンプレのソースを載せる。
EDPC N Slimes
dp[a][b] := [a, b]のスライムを合体させたときにかかる最低コストと定める。
漸化式は、dp[a][b] = min(dp[a][c] + dp[c + 1][b]) + 区間[a, b]でのスライムの質量の和
やっていることとしては、今見てる区間をを2つの区間に分割して、それぞれの子区間でのコストの和が最小のものを考える。区間[a, b]のスライムを合体させることは、子区間の取り方によらず質量は一定なので、累積和で前計算しておきO(1)で求まるようにすれば、漸化式は立つ。
漸化式は、dp[a][b] = min(dp[a][c] + dp[c + 1][b]) + 区間[a, b]でのスライムの質量の和
やっていることとしては、今見てる区間をを2つの区間に分割して、それぞれの子区間でのコストの和が最小のものを考える。区間[a, b]のスライムを合体させることは、子区間の取り方によらず質量は一定なので、累積和で前計算しておきO(1)で求まるようにすれば、漸化式は立つ。
サンプルソースでは、iループでは更新する区間の長さを定めてる。区間の長さが短い方から更新していく。
jループは区間の始点を回している。終了条件をあのように書くとわかりやすい。
kループは漸化式の更新。
jループは区間の始点を回している。終了条件をあのように書くとわかりやすい。
kループは漸化式の更新。
