提出 #24437899

---

ソースコード 拡げる

import sys

def main(f):
  N = int(f.readline())
  A = [None] + list(map(int, f.readline().split()))
  S = [0] * (N+1)
  for i in range(1, N+1):
    S[i] = S[i-1] + A[i]

  dp = [[None] * (N+1) for _ in range(N+1)] # dp[i][j] : a_i 〜 a_j を使った場合の答え
  # d = 1
  for i in range(1, N+1):
    dp[i][i] = 0

  for d in range(2, N+1): # 幅dの部分列について計算
    for i in range(1, N+2-d):
      j = i + d - 1
      min_cost = -1
      for k in range(i, j): # 最後に結合する場所で場合分け
        cost = dp[i][k] + dp[k+1][j] + S[j] - S[i-1] # sum(A[i:j+1])
        if min_cost < 0 or cost < min_cost:
          min_cost = cost
      dp[i][j] = min_cost
  print(dp[1][N])

main(sys.stdin)

提出情報

ジャッジ結果