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):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools


def input():
    return sys.stdin.readline().strip("\n").strip(" ")

_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12
INF = 10**20

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():



    N = iip()
    A = iip()
    SA = [0]

    cur = 0
    for i in A:
        cur += i
        SA.append(cur)

    
    size = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(i, N):
            size[i][j] = int(SA[j+1]-SA[i])

    

    dp = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for d in range(N):
        for l in range(N):
            r = l+d
            if r >= N:
                continue

            if l==r:
                dp[l][r] = 0
            else:
                dp[l][r] = min(dp[l][r],
                               dp[l+1][r] + size[l][l] + size[l+1][r],
                               dp[l][r-1] + size[r][r] + size[l][r-1])

            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + size[l][k] + size[k+1][r])

    
    print(dp[0][-1])








def kiriage_warizan(a, b):
    return -(-a//b)

def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True):  
    if isinstance(l, list):
        l = l[0] 
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools


def input():
    return sys.stdin.readline().strip("\n").strip(" ")

_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12
INF = 10**30

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():



    N = iip()
    A = iip()
    SA = [0]

    cur = 0
    for i in A:
        cur += i
        SA.append(cur)

    
    size = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(i, N):
            size[i][j] = int(SA[j+1]-SA[i])

    

    dp = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for d in range(N):
        for l in range(N):
            r = l+d
            if r >= N:
                continue

            if l==r:
                dp[l][r] = 0
            else:
                dp[l][r] = min(dp[l][r],
                               dp[l+1][r] + size[l][l] + size[l+1][r],
                               dp[l][r-1] + size[r][r] + size[l][r-1])

            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + size[l][k] + size[k+1][r])

    
    print(dp[0][-1])








def kiriage_warizan(a, b):
    return -(-a//b)

def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True):  
    if isinstance(l, list):
        l = l[0] 
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools


def input():
    return sys.stdin.readline().strip("\n").strip(" ")

_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():



    N = iip()
    A = iip()
    SA = [0]

    cur = 0
    for i in A:
        cur += i
        SA.append(cur)

    
    size = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(i, N):
            size[i][j] = int(SA[j+1]-SA[i])

    

    dp = [[10**13 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for d in range(N):
        for l in range(N):
            r = l+d
            if r >= N:
                continue

            if l==r:
                dp[l][r] = 0
            else:
                dp[l][r] = min(dp[l][r],
                               dp[l+1][r] + size[l][l] + size[l+1][r],
                               dp[l][r-1] + size[r][r] + size[l][r-1])

            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + size[l][k] + size[k+1][r])

    
    print(dp[0][-1])








def kiriage_warizan(a, b):
    return -(-a//b)

def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True):  
    if isinstance(l, list):
        l = l[0] 
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [[0]*(n+2) for i in range(n+2)]

suma = [[0]*(n+2) for i in range(n+2)]

for i in range(n):
    suma[i][i+1] = a[i]
    for j in range(i+2,n+1):
        suma[i][j] = suma[i][j-1]+a[j-1]

for i in range(2,n+1):
    for l in range(n-i+1):
        r = i+l
        dp[l][r] = float("INF")
        for k in range(l+1,r):
            dp[l][r] = min(dp[l][r],dp[l][k]+dp[k][r]+suma[l][r])
print(dp[0][n])

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
dp = [[[0,0] for j in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i] = [a[i],0]
for i in range(1,N):
    for j in range(N-i):
        Num = 0
        Num2 = 10**13
        for k in range(j, j+i):
            num2 = dp[j][k][1]+dp[k+1][j+i][1]+dp[j][k][0]+dp[k+1][j+i][0]
            if Num2 > num2:
                Num2 = num2
                Num = dp[j][k][0]+dp[k+1][j+i][0]
        dp[j][j+i] = [Num, Num2]
print(dp[0][N-1][1])

Solution (Python):
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 = [[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))

Solution (Python):
import sys
import itertools
input = sys.stdin.readline

n=int(input())
a= list(map(int, input().split()))
a+=a
b=itertools.accumulate(a)
b=[0]+list(b)
INF=10**15
dp=[[INF] *(2*n+1) for i in range(2*n+1)]



for i in range(n):
    for l in range(2*n-i):
        r=l+i
        if r==l:
            dp[l][r]=0
        else:
            
            for k in range(l,r):
                dp[l][r]=min(dp[l][k]+dp[k+1][r]+b[r+1]-b[l],dp[l][r])

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

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

if N == 2:
    print(sum(a))
    exit()

a_cum = [0, a[0]]
for i in range(1,N):
    a_cum.append(a_cum[-1] + a[i])

def a_sum(i,j):
    return a_cum[j] - a_cum[i]

INF = 10**15

dp = [[INF]*(N+1) for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = 0
    if i != N-1:
        dp[i][i+2] = a[i] + a[i+1]

for length in range(3, N+1):
    for l in range(N-length+1):
        tmp = INF
        for m in range(l+1, l+length):
            tmp = min(tmp, dp[l][m] + dp[m][l+length] + a_sum(l, l+length))
        dp[l][l+length] = tmp

print(dp[0][N])

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


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

a_accum = [0]
for i in range(n):
    a_accum.append(a_accum[-1] + a[i])

for k in range(2, n+1):
    for i in range(n-k+1):
        mini = 10**15
        for j in range(i+1, i+k):
            mini = min(dp[i][j] + dp[j][i+k], mini)
        dp[i][i+k] = mini + a_accum[i+k]-a_accum[i]
print(dp[0][n])

Solution (Python):
from itertools import accumulate


def dfs(l, r):
    if memo[l][r]:
        return dp[l][r]
    for i in range(l, r):
        dp[l][r] = min(max(0, dp[l][r]), dfs(l, i) + dfs(i + 1, r) + acc_A[r] - acc_A[l - 1])
    memo[l][r] = True
    return dp[l][r]


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

INF = 10 ** 18
dp = [[INF] * (n + 1) for _ in range(n + 1)]
memo = [[False] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][i] = 0
    memo[i][i] = True


print(dfs(1, n))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))

    b = [0]
    for num in a:
        b.append(b[-1]+num)
    
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    
    for i in range(2,N+1):
        for j in range(N-i+1):
            dp[j][i] = min(dp[j][k]+dp[j+k][i-k] for k in range(1,i))+b[i+j]-b[j] 
    
    print(dp[0][-1])
        
if __name__ == "__main__":
    main()

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

asum = [0]*(n+1)
for i in range(n):
    asum[i+1] = asum[i] + a[i]

dp = [[1e100]*(n+1) for _ in range(n+1)]

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

for j in range(2,n+1):
    for i in range(n+1-j):
        temp = 1e100
        for k in range(1,j):
            temp = min(temp, dp[i][i+k] + dp[i+k][i+j] + asum[i+j] - asum[i])
        dp[i][i+j] = temp
print(dp[0][n])

Solution (Python):
from itertools import accumulate

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

dp = [[0 for _ in range(N+1)] for _ in range(N)]
acc = [0] + list(accumulate(A))

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)]) + acc[r] - acc[l]

print(dp[0][N])

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
dp = [[float("inf")] * N for _ in range(N)]
k = [[-1] * N for _ in range(N)]
cs = [0] * (N + 1)
for i in range(N):
  cs[i + 1] = cs[i] + a[i]
  k[i][i] = i
  dp[i][i] = 0

def mongedp():
  global dp
  global k
  for d in range(1, N):
    for i in range(N):
      if i + d >= N: continue
      j = i + d
      for t in range(k[i][j - 1], min(k[i + 1][j] + 1, j)):
        temp = dp[i][t] + dp[t + 1][j] + cs[j + 1] - cs[i]
        if temp < dp[i][j]:
          dp[i][j] = temp
          k[i][j] = t
mongedp()
print(dp[0][-1])

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

dp = [[0]*440 for i in range(440)]
s = [[0]*440 for i in range(440)]
for l in range(n):
    s[l][l+1] = a[l]
    for r in range(l+2,n+1):
        s[l][r] = s[l][r-1] + a[r-1]

for width in range(2,n+1):
    for l in range(n-width+1):
        r = l + width
        dp[l][r] = float('inf')
        for m in range(l+1,r):
            dp[l][r] = min(dp[l][r], dp[l][m] + dp[m][r] + s[l][r])

print(dp[0][n])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10**9+7
INF = 10 ** 20
from functools  import lru_cache

MAXN = 405
a = [0] * MAXN
dp = [[-1] * MAXN for _ in range(MAXN)]
def dfs(l,r):
    if dp[l][r] != -1:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = 0
        return 0
    ans = INF
    for i in range(l + 1,r):
        ans = min(ans,dfs(l,i) + dfs(i,r)) 
    if l == 0:
        ans += a[r - 1]
    else:
        ans += a[r - 1] - a[l - 1]
    dp[l][r] = ans
    return ans

def main():
    n = int(input())
    b = list(map(int,input().split()))
    a[:n] = b

    for i in range(1,n):
        a[i] += a[i - 1]
    
    ans = dfs(0,n)
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
from itertools import accumulate
 
n = int(input())
acc = [0] + list(accumulate(map(int, input().split())))
dp = [[0] * (n + 1) for _ 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)) + acc[r] - acc[l]
print(dp[0][n])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=[0]*(N+1)
for i in range(N):
  B[i+1]=B[i]+A[i]

dp=[[0]*(N+1) for i in range(N)]

for k in range(2,N+1):
  
  for i in range(N-k+1):
    dp[i][k]=min(dp[i][j]+dp[i+j][k-j] for j in range(1,k))+B[i+k]-B[i]
print(dp[0][N])