# dp[l][r]=min(区間[l,r]を合成するための最小コスト)

n=int(eval(input()))

a=list(map(int,input().split()))

INF=10**15

dp=[[0]*n for i in range(n)]

for i in range(n):

    dp[i][i]=a[i]

# 合成するときの必要経費を構成

for i in range(n-1):

    for j in range(i+1,n):

        dp[i][j]=dp[i][j-1]+a[j]

dp[0][-1]=0

# dp[i][j]=min(dp[i][k]+dp[k+1][j])+必要経費 で斜め(0,1),(1,2),(0,2),(1,3),...の順に見ていく

# ループの書き方に手間取った

for i in range(1,n):

    for j in range(n-i):

        ans=INF

        for k in range(j,i+j):

            ans=min(ans,dp[j][k]+dp[k+1][i+j])

        dp[j][i+j]+=ans

print((dp[0][-1]))
# 大きさがsum(a)のスライムが1匹いる

# dp[l][r]=min(区間[l,r]を分解するための最小コスト)

import sys

sys.setrecursionlimit(1000000000)

input = sys.stdin.readline

INF=10**15

n=int(eval(input()))

a=list(map(int,input().split()))

b=[0]*(n+1)

for i in range(n):

    b[i+1]=b[i]+a[i]

dp=[[-1]*n for i in range(n)]

for i in range(n):

    dp[i][i]=0

def memo(i,j):

    if dp[i][j]>=0:

        return dp[i][j]

    ans=INF

    for k in range(i,j):

        ans=min(ans,memo(i,k)+memo(k+1,j))

    dp[i][j]=ans+b[j+1]-b[i]

    return dp[i][j]

print((memo(0,n-1)))
# dp[l][r]=min(区間[l,r]を合成するための最小コスト)
n = int(eval(input()))
a = list(map(int, input().split()))
INF = 10**15
dp = [[0] * n for i in range(n)]
for i in range(n):
    dp[i][i] = a[i]
# 合成するときの必要経費を構成
for i in range(n - 1):
    for j in range(i + 1, n):
        dp[i][j] = dp[i][j - 1] + a[j]
dp[0][-1] = 0
# dp[i][j]=min(dp[i][k]+dp[k+1][j])+必要経費 で斜め(0,1),(1,2),(0,2),(1,3),...の順に見ていく
# ループの書き方に手間取った
for i in range(1, n):
    for j in range(n - i):
        ans = INF
        for k in range(j, i + j):
            ans = min(ans, dp[j][k] + dp[k + 1][i + j])
        dp[j][i + j] += ans
print((dp[0][-1]))

# 大きさがsum(a)のスライムが1匹いる
# dp[l][r]=min(区間[l,r]を分解するための最小コスト)
import sys

sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
INF = 10**15
n = int(eval(input()))
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
dp = [[-1] * n for i in range(n)]
for i in range(n):
    dp[i][i] = 0


def memo(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    ans = INF
    for k in range(i, j):
        ans = min(ans, memo(i, k) + memo(k + 1, j))
    dp[i][j] = ans + b[j + 1] - b[i]
    return dp[i][j]


print((memo(0, n - 1)))

-# dp[l][r]=min(区間[l,r]を合成するための最小コスト) +# 大きさがsum(a)のスライムが1匹いる +# dp[l][r]=min(区間[l,r]を分解するための最小コスト) +import sys + +sys.setrecursionlimit(1000000000) +input = sys.stdin.readline +INF = 10**15 -INF = 10**15 -dp = [[0] * n for i in range(n)] +b = [0] * (n + 1) -    dp[i][i] = a[i] -# 合成するときの必要経費を構成 -for i in range(n - 1): -    for j in range(i + 1, n): -        dp[i][j] = dp[i][j - 1] + a[j] -dp[0][-1] = 0 -# dp[i][j]=min(dp[i][k]+dp[k+1][j])+必要経費 で斜め(0,1),(1,2),(0,2),(1,3),...の順に見ていく -# ループの書き方に手間取った -for i in range(1, n): -    for j in range(n - i): -        ans = INF -        for k in range(j, i + j): -            ans = min(ans, dp[j][k] + dp[k + 1][i + j]) -        dp[j][i + j] += ans -print((dp[0][-1])) +    b[i + 1] = b[i] + a[i] +dp = [[-1] * n for i in range(n)] +for i in range(n): +    dp[i][i] = 0 + + +def memo(i, j): +    if dp[i][j] >= 0: +        return dp[i][j] +    ans = INF +    for k in range(i, j): +        ans = min(ans, memo(i, k) + memo(k + 1, j)) +    dp[i][j] = ans + b[j + 1] - b[i] +    return dp[i][j] + + +print((memo(0, n - 1)))