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}

まず、累積和を作る。

sum: {0, 10, 30, 60, 100}

dp[l][r] を、区間 a[l] から a[r] までのスライムを合体させる最小コストとする。

残り $1$ 匹の場合、合体する必要がないのでコストは $0$ である。

たとえば、dp[2][3] を考える。
この区間は a[2] と a[3] だけなので、最後にその $2$ 匹を合体させるしかない。

dp[2][3] = dp[2][2] + dp[3][3] + (sum[4] - sum[2])
         = 0 + 0 + 70
         = 70

この提出コードでは、表の下段から順に、左から埋めていく。
具体的には、次の順に値が確定する。

dp[2][3]
dp[1][2] -> dp[1][3]
dp[0][1] -> dp[0][2] -> dp[0][3]

dp[0][3] では、最後に合体する境界を全て試す。

dp[0][3] = min(
  dp[0][0] + dp[1][3],
  dp[0][1] + dp[2][3],
  dp[0][2] + dp[3][3]
) + (sum[4] - sum[0])

それぞれの値を入れると、次のようになる。

dp[0][3] = min(0 + 140, 30 + 70, 90 + 0) + 100
         = min(140, 100, 90) + 100
         = 190

実際に埋めると、次のようになる。

右上の $190$ が答えである。

注意点

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

別解

特になし。