N – Slimes 解説 (Educational DP Contest / DP まとめコンテスト)

2020年3月10日AtCoderDP, 競プロ, 区間DP, 区間の除去・圧縮・合体

問題へのリンク

問題概要

N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。

  • 隣り合う2つ \(a, b\) を選んで取り除き、かわりに a+b を置く。この時コスト a+b を払う

支払うコストの合計の最小値はいくつになるか?

制約

  • \(2 \leq N \leq 400\)
  • \(1 \leq a_i \leq 10^9\)

考え方

「区間の除去・圧縮・合体」などがあるときは、区間DP を用いると上手くいくことがあります。

典型的な区間DPの形に合わせると、以下のようなDPになります。

\(dp[ l ][ r ]\) := 区間 [ l, r ) について、1つになるまで操作を行った時の支払うコストの合計の最小値

更新は以下のようにすれば良いです。

  • dp[ l ][ r ] = min( dp[ l ][ i ] + dp[ i ][ r ] +「 区間 [ l, r )の合計値」 )

区間を2つに分けて、それぞれの区間を1つにまとめてから、できた2つを最終的に1つにまとめています。

この時支払うコストはどのようなまとめ方をしても、 「区間 [ l, r )の合計値」に等しいです。

区間の合計値を累積和などで別に用意しておくか、dp の配列にまとめて保存しておくと良いでしょう。

C++ での実装例

区間DPは for 文で実装するのが難しいので、メモ化再帰で実装するのがおすすめです。

区間の合計値は配列にまとめて保持しています。