[学習記録]AtCoder EDP N-Slimes[Go]

問題

N 匹のスライムが横一列に並んでいます。 最初、左から i 番目のスライムの大きさは ai​ です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

• 左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 合体前の 2 匹のスライムの大きさを x および y とすると、合体後のスライムの大きさは x+y となる。 このとき、太郎君は x+y のコストを支払う。 なお、合体の前後でスライムたちの位置関係は変わらない。

太郎君が支払うコストの総和の最小値を求めてください。

解法

払ったコストの最小をDPに保存しておけば計算が可能そう。
常に隣り合ったスライムを合体させるので、状態は left, rightで持つことができそう。
入力例１のとき、最後の１回の合体を考えると、
それまで払ったコスト　＋　合体後の大きさ　となり、
それまで払ったコスト
    ＝　10 +  [ 20 + 30 + 40 ]
        or  [ 10  + 20  ]   +   [  30 + 40 ]
        or  [ 10 + 20 + 30 ] + 40
　　の最小値
合体後の大きさ
     =   1 番目から n 番目までの大きさを足した値
となる。
再帰的に計算していけば答えが求められそう。

n := readInt()
sli = readSli(n)
dp = make([][]int, n)
memo = make([][]bool, n) // 再帰なのでメモを取っておく
for i := 0; i < n; i++ {
	dp[i] = make([]int, n)
	memo[i] = make([]bool, n)
}
ans := calculate(0, n-1)
return ans

それまで払ったコストは、与えられたスライムの位置の内、
どこで分割するかを全て計算し、その最少を取ることで計算できる。
left と right が同じときは合成しない　→　コスト　＝　０になる

func calculate(l, r int) int {
	if memo[l][r] {
		return dp[l][r]
	}
	memo[l][r] = true

	if l == r {
		return 0
	}

	min := max_int64
　　// i を変化させることで分割位置を変化させている
    // left: l ～ i まで、 right: i+1 ～ rまで
	for i := l; i < r; i++ {
		min = Min(min, calculate(l, i)+calculate(i+1, r))
	}
}

合体後の大きさは、 left から right まで足せばいいが、それを毎回やっていると時間が足りなくなるので累積和を用い る。
あとは計算結果としてDPを返せば、答えが得られる

func run() interface{} {

    // ...

	cum = make([]int, n+1)
	for i := 1; i <= n; i++ {
		cum[i] = cum[i-1] + sli[i-1]
	}

	ans := calculate(0, n-1)
	return ans
}

func calculate(l, r int) int {
    // ...

	min := max_int64
	for i := l; i < r; i++ {
		min = Min(min, calculate(l, i)+calculate(i+1, r))
	}

    // それまで払ったコスト　＋　合体後の大きさ
	dp[l][r] = min + cum[r+1] - cum[l]

	return dp[l][r]
}

コード（AC)

func run() interface{} {
	n := readInt()

	sli = readSli(n)
	dp = make([][]int, n)
	memo = make([][]bool, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		memo[i] = make([]bool, n)
	}

	cum = make([]int, n+1)
	for i := 1; i <= n; i++ {
		cum[i] = cum[i-1] + sli[i-1]
	}

	ans := calculate(0, n-1)
	return ans
}

func calculate(l, r int) int {
	if memo[l][r] {
		return dp[l][r]
	}
	memo[l][r] = true

	if l == r {
		return 0
	}

	min := max_int64
	for i := l; i < r; i++ {
		min = Min(min, calculate(l, i)+calculate(i+1, r))
	}

	dp[l][r] = min + cum[r+1] - cum[l]

	return dp[l][r]
}