EDPC N - Slimes

考え方

ABCでいうと、E問題級。

基本的にはただの区間 DP で、L 問題と同じように解けばよい。
ただし、「今回の合体コスト」を計算するときに長大な和を取る必要がある。
そのため、累積和のアルゴリズムを同時に用いる。

dp[l][r] を、l 番目から r 番目までのスライムを合体させる場合の最小コストとする。
最後に合体する境界を全パターン試すと、次の形になる。

dp[l][r] = min(dp[l][m-1] + dp[m][r]) + 区間全体の大きさ

区間全体の大きさは、累積和を使って求めればよい。

計算量は $O(N^3)$。

入力例1での動作

入力を受け取る。

n: 4
a: {10, 20, 30, 40}

区間の大きさをすぐ求められるように、累積和を作る。

{0, 10, 30, 60, 100}

例えば $\{30,40\}$ の大きさは、累積和の差 $100-30=70$ で求められる。

区間ごとに、その範囲のスライムを $1$ 匹にまとめる最小コストを考える。

スライムが $1$ 匹だけなら、合体する必要がない。
そのため、コストは $0$ である。

まず、$\{30,40\}$ の区間を考える。

この $2$ 匹を最後に合体させるしかない。
区間全体の大きさは、累積和から $100-30=70$ である。
したがって、最小コストは $70$ となる。

次に、$\{20,30,40\}$ の区間を考える。

最後の合体の直前には、$\{20\}$ と $\{30,40\}$ に分かれている場合がある。
この場合、それまでのコストは $0+70=70$ である。

もう一つは、$\{20,30\}$ と $\{40\}$ に分かれている場合である。
この場合、それまでのコストは $50+0=50$ である。

区間全体の大きさは、累積和から $100-10=90$ である。
したがって、最小コストは $50+90=140$ となる。

最後に、全体 $\{10,20,30,40\}$ を考える。
最後の合体の直前の分け方は $3$ 通りある。

この中では $90$ が最小である。

全体の大きさは、累積和から $100-0=100$ である。
最後の合体コストとしてこれを加えるので、最小コストは $90+100=190$ となる。

全ての区間について求めると、次の表になる。

全体の最小コストは $190$ である。
したがって、答えは $190$。

注意点

答えは、int 型からはみ出る。
DP テーブルを含め、long long 型を用いること。

別解

特になし。