Problem:
 Score : 100 points    Problem Statement There are N slimes lining up in a row.
Initially, the i -th slime from the left has a size of a_i .  Taro is trying to combine all the slimes into a larger slime.
He will perform the following operation repeatedly until there is only one slime:   Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x + y , where x and y are the sizes of the slimes before combining them. Here, a cost of x + y is incurred. The positional relationship of the slimes does not change while combining slimes.   Find the minimum possible total cost incurred.      Constraints  All values in input are integers.  2 \leq N \leq 400  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  \ldots  a_N       Output Print the minimum possible total cost incurred.        Sample Input 1 4
10 20 30 40      Sample Output 1 190  Taro should do as follows (slimes being combined are shown in bold):   ( 10 , 20 , 30, 40) → ( 30 , 30, 40)  ( 30 , 30 , 40) → ( 60 , 40)  ( 60 , 40 ) → ( 100 )        Sample Input 2 5
10 10 10 10 10      Sample Output 2 120  Taro should do, for example, as follows:   ( 10 , 10 , 10, 10, 10) → ( 20 , 10, 10, 10)  (20, 10 , 10 , 10) → (20, 20 , 10)  (20, 20 , 10 ) → (20, 30 )  ( 20 , 30 ) → ( 50 )        Sample Input 3 3
1000000000 1000000000 1000000000      Sample Output 3 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 4 6
7 6 8 6 1 1      Sample Output 4 68  Taro should do, for example, as follows:   (7, 6, 8, 6, 1 , 1 ) → (7, 6, 8, 6, 2 )  (7, 6, 8, 6 , 2 ) → (7, 6, 8, 8 )  ( 7 , 6 , 8, 8) → ( 13 , 8, 8)  (13, 8 , 8 ) → (13, 16 )  ( 13 , 16 ) → ( 29 )

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [0] + list(accumulate(a))
dp = [[inf]*(n) for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
for l in range(n-1)[::-1]:
    for r in range(l+1,n):
        s = b[r+1] - b[l]
        for c in range(l,r):
            dp[l][r] = min(dp[l][r],s + dp[l][c] + dp[c+1][r])
print(dp[0][-1])

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [0] + list(accumulate(a))
dp = [[inf]*(n) for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
for l in range(n-1)[::-1]:
    for r in range(l+1,n):
        s = b[r+1] - b[l]
        if r - l == 1:
            dp[l][r] = s
            continue
        for c in range(l,r):
            dp[l][r] = min(dp[l][r],s + dp[l][c] + dp[c+1][r])
print(dp[0][-1])

Solution (Python):

from itertools import accumulate

n=int(input())
a=[0]+list(accumulate(map(int,input().split())))
dp=[[0]*(n+1) for i in range(n)]
for w in range(2,n+1):
    for l in range(n-w+1):
        r=l+w
        dp[l][r]=min(dp[l][m]+dp[m][r] for m in range(l+1,r)) + a[r]-a[l]
print(dp[0][n])

Solution (Python):
N = int(input())
a = [int(x) for x in input().split()]

cumsum = [0] * N
cumsum[0] = a[0]
for i in range(1, N):
    cumsum[i] = cumsum[i-1] + a[i]

dp = [[0] * N for _ in range(N)]

for j in range(1, N):
    for i in range(N-1):
        if i + j >= N:
            break
        minimum = float('inf')
        for k in range(j):
            
            temp = dp[i][k] + dp[i+k+1][j-k-1]
            if minimum > temp:
                minimum = temp
        dp[i][j] = minimum + (cumsum[i+j] - cumsum[i-1] if i > 0 else cumsum[i+j])

print(dp[0][N-1])

Solution (Python):
inf = 10 ** 16

n = int(input())
a = tuple(int(x) for x in input().split())

d = [[inf] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0

c = [0]
for aa in a:
    c.append(c[-1] + aa)

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            
            d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j])
        d[i][j] += c[j + 1] - c[i]


print(d[0][n - 1])

Solution (Python):
inf = float('inf')

n = int(input())
a = tuple(int(x) for x in input().split())

d = [[inf] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0

c = [0]
for aa in a:
    c.append(c[-1] + aa)

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            
            d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j])
        d[i][j] += c[j + 1] - c[i]


print(d[0][n - 1])

Solution (Python):
import heapq
n = int(input())

a = list(map(int, input().split( )))
a.append(0)
lrg =10**13
dp= [[lrg]*n for _ in range(n)]

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

s = [[0]*(n+1) for i in range(n+1)]
for i in range(n+1):
    for j in range(i,n):
        s[i][j] = sum(a[i:j+1])


for d in range(n):
    for i in range(n-d):
        for k in range(d):
            dp[i][i+d] = min(dp[i][i+d],dp[i][i+k]+dp[i+k+1][i+d]+s[i][i+d])


print(dp[0][n-1])

Solution (Python):
import numpy as np

N = int(input())
A = np.array(input().split(), np.int64)

Acum = np.zeros((N, N + 1), dtype=np.int64)
for i in range(N):
    Acum[i, i + 1:] = A[i:].cumsum()

dp = np.zeros((N, N + 1), dtype=np.int64)

for length in range(2, N + 1):
    for left in range(N - length + 1):
        right = left + length
        dp[left, right] = (dp[left, left + 1: right] + dp[left + 1: right, right]).min() + Acum[left, right]

print(dp[0, N])

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

dp = [[10**18]*N for i in range(N)]

cA = [0]*(N+1)
for i in range(1,N+1) :
    cA[i] = cA[i-1] + A[i-1]

    dp[i-1][i-1] = 0

for d in range(1,N) :
    for i in range(N-d) :
        for cut in range(i, i+d) :
            dp[i][i+d] = min(dp[i][i+d], dp[i][cut] + dp[cut+1][i+d] + cA[i+d+1] - cA[i])

ans = dp[0][N-1]

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])

def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return


def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return


def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return


def E():
    n = I()
    a = LIR(n)
    b = [1<<i for i in range(n+1)]
    dp = [0 for i in range(b[n])]
    dp[0] = 1
    for i in range(n):
        for k in range(b[n])[::-1]:
            for j in range(n):
                if a[i][j] and not b[j]&k:
                    dp[b[j]|k] += dp[k]
                    dp[b[j]|k] %= mod
    print(dp[-1])

def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
INF = float('inf')
N = int(input())
a = [0]+[int(x) for x in input().split()]
for i in range(N):
    a[i+1] += a[i]
dp = [[INF] * N for i in range(N)]
for i in range(N):
    dp[i][i] = 0
for k in range(1, N):
    for i in range(N-k):
        for j in range(k):
            dp[i][i+k] = min(dp[i][i+k], dp[i][i+j]+dp[i+j+1][i+k]+a[i+k+1]-a[i])
print(dp[0][N-1])

Solution (Python):
N = int(input())
a = list(map(int, input().split()))

A = [[0 for __ in range(N)] for _ in range(N)]
S = [[0 for __ in range(N)] for _ in range(N)]

for i in range(N-1):
    for j in range(i, N):
        S[i][j] = sum(a[i:j+1])

for w in range(1, N):
    for i in range(N):
        j = i + w
        if j >= N:
            break
        
        A[i][j] = min([
            A[i][k] + A[k+1][j] for k in range(i, j)
        ]) + S[i][j]

print(A[0][-1])

Solution (Python):
from numpy import*
n,a=open(0)
n=int(n)
a=cumsum(int64([0]+a.split()))
dp=zeros((n,n+1),'i8')
for k in range(1,n):
  l=arange(n-k)
  r=arange(k+1,n+1)
  m=(arange(1,k+1)+l[:,newaxis]).T
  dp[l,r]=amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
print(dp[0,n])

Solution (Python):
from numpy import*
n,a=open(0)
n=int(n)
a=cumsum(int64([0]+a.split()))
dp=zeros((n,n+1),'i8')
for k in range(1,n):
  l=arange(n-k)
  r=arange(k+1,n+1)
  m=array([arange(i+1,i+k+1)for i in range(n-k)]).T
  dp[l,r]=amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
print(dp[0,n])

Solution (Python):
from numpy import*
n,a=open(0)
n=int(n)
a=cumsum(int64([0]+a.split()))
dp=zeros((n,n+1),'i8')
for k in range(1,n):
  for l in range(n-k):
    r=l+k+1
    dp[l,r]=amin(dp[l,l+1:r]+dp[l+1:r,r],0)+a[r]-a[l]
print(dp[0,n])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main():
  def s(l,r):
    k=l*n+r
    if d[k]:return d[k]
    if r-l<2:return 0
    d[k]=t=min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
    return t
  n,*a=map(int,open(0).read().split())
  d=[None]*(n*n+1)
  for i in range(n-1):a[i+1]+=a[i]
  a+=[0]
  print(s(0,n))
main()