EDPC N - Slimes - あっとのTECH LOG

問題原文

問題要旨

$N$ 匹のスライムが横１列に並んでいる。 $i$ 番目のスライムの大きさは $A_i$ である。
スライムが１匹になるまで以下の操作を繰り返す。

隣り合うスライムをくっつけて１匹のスライムにする。このとき、くっつける前のスライムの大きさをそれぞれ $x$ , $y$ とすると、くっつけた後のスライムの大きさは $x + y$ になり、またコストが $x + y$ かかる。

スライムを１匹にするまでのコストを最小化せよ。

$1 \leq N \leq 400$

解法

区間dpの基礎問題らしいので解いてみた。
$dp[i\rbrack[j\rbrack :=$ 区間 [i, j] のスライムを１匹にする場合の最小コストとする。
これはある $i \leq x \leq j - 1$ を満たすスライム $x$ までで、求めたい区間に対する答えを区間[i, x] と区間[x + 1, j] に対する問題へと分割することで以下再帰的に求められる。

実際のコストは、二つの区間の答えに [i, j] の区間のスライムの大きさを足し合わせたものになる。
これは累積和で計算できる。

実装

ぎこちないったらありゃしない。dpテーブルは半開区間で持った方がよかったな。。。
更新順で頭が壊れたのでメモ化再帰で解いた。

import sys
from itertools import accumulate
sys.setrecursionlimit(10 ** 9)

N = int(input())
A = list(map(int, input().split()))
acc = [0] + list(accumulate(A))

# dp[i][j] := 区間[i, j]のスライムたちを１匹にまとめるのに必要なコスト
dp = [[None] * N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(i, j):
    if j - i == 1:
        dp[i][j] = A[i] + A[j]
        return dp[i][j]

    if dp[i][j] is not None:
        return dp[i][j]

    ret = float('inf')
    for x in range(i, j):
        ret = min(ret, dfs(i, x) + dfs(x + 1, j) + acc[j + 1] - acc[i])

    dp[i][j] = ret
    return ret


print(dfs(0, N - 1))

感想

ちょっと理解したけどまだまだという感じ。
時間空けてときなおしてみよう。