https://atcoder.jp/contests/dp/submissions/11718958
一見どんな順番で合成しても同じように感じるが、それだと問題にならないので合成する順番によって答えに差が出る（ぇ
他人の解説を見るまで気づかなかったが、最初に足したものが何度も足されるため、最初のうちは小さいスライムを合成したほうが小さい合計値になる。
- 初期値はrep(i, 0, N) dp[i][i] = 0;
- 繰り返しは幅wと区間開始iと分割境界j
- rep(w, 1, N) rep(i, 0, N) rep(j, i + 1, i + w + 1)
- 状態は特になし
- 漸化式はdp[i][i + w] = min(dp[i][i + w], dp[i][j - 1] + dp[j][i + w] + sum);
- 最終目標はdp[0][N-1]
どのように全探索すれば良いかというと区間DPという考え方を使う。dp[l][r]を閉区間[l,r]のスライムを合成したときの値とする。更に区間[l,r]の幅をwとする。区間[l,l+w]に対してjを境界として[l,j-1]と[j, l+w]の2つに分割する。
dp[i][i + w] = min(dp[i][i + w], dp[i][j - 1] + dp[j][i + w] + sum);
この漸化式を区間幅w=1からw=Nまで全探索する。合成される図を注意深く見ると、区間の合成値=左の区間最善値+右の区間最善値+左右あわせた区間内のスライム合計値(sum)になっている。何も工夫しないとで間に合わないが、スライムの累積和テーブルを予め用意しておくことでsumがO(1)になって通る。
