DPまとめコン N Slimes

例の表

https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0

所感

DPだってわかっていれば行ける系

問題概要

N個の整数を持つスライムが与えられる。以下の操作を繰り返した時のコストの最小値をもとめよ。
隣り合ったスライムa, bを合成し、a+b と置き換える。この時、a+b のコストがかかる。これをスライムが1つになるまで繰り返す。

取った方針

DPだとわかっているので、DP[l][r] := 区間[l,r]のスライムを合体するときの最小コスト なるDPが降ってくる。
この時、更新は[l,r]を二つの区間[l,m], [m+1,r] に分けて、mを全探索することで求まる。更新式はイカ。
DP[l][r] = min(DP[l][m] + DP[m+1][r]) + sum(l,r)
ここで、min(DP[l][m] + DP[m+1][r])はDP[l][m] + DP[m+1][r]が最小となるmを取った時のDP[l][m] + DP[m+1][r]の値、sum(l,r)は[l,r]に含まれる値を全部足したものを表す。
sum(l,r)はO(N)で累積和を求めておけばO(1)で求まるので、DPの表のマスがO(N²)、1マス埋めるのに愚直に全探索してO(N) かかるので、O(N³)で間に合う。

正しい方針

同上

得られた知見

・これが区間DPってやつですか
・区間ごとに複数求まる値の最大/最小値 -> dp[l][r] を[l,r] なる区間の最大/最小値 とするDP

解くのに必要な要素

・区間DP

周辺調査によって得られた知見

特になし