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)



Sample input:
4
10 20 30 40


Sample output:
190

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC N

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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC N

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])

Submission status: Accepted

Solution code:
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2
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])

Submission status: Accepted

Solution code:
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):
            # [i, k], (k, 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)
# print(c)
print(d[0][n - 1])

Submission status: Accepted

Solution code:
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):
            # [i, k], (k, 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)
# print(c)
print(d[0][n - 1])

Submission status: Accepted

Solution code:
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 #
    #dp[i][i+1] = a[i]+a[i+1]
#dp[n-1][n-1] = 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 i in range(n+1):
#  	print(*s[i])
for d in range(n):#n-1ではない
    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])###
#for i in range(n):
#  	print(*dp[i])
print(dp[0][n-1])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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


#A
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]])
#B
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

#C
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

#D
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

#E
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])
#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])