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: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1000000007
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

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

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

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = dict()
for i in range(N):
    dp[i, i + 1] = 0

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

print(dp[0, N])

Submission status: Time Limit Exceeded

Solution code:
def rec(frm, to):
    """return: [frm,to)の合体コスト最小値"""
    if to - frm == 1:
        return 0

    if memo[frm][to]:
        return memo[frm][to]

    res = inf
    for mid in range(frm + 1, to):
        res = min(res, rec(frm, mid) + rec(mid, to))
    res += cum_sum[to] - cum_sum[frm]

    memo[frm][to] = res
    return res


inf = float('inf')

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

cum_sum = [0] * (n + 1)
for i, aa in enumerate(a):
    cum_sum[i + 1] = cum_sum[i] + aa

memo = [[None] * (n + 1) for _ in range(n + 1)]
# memo[frm][to] = メモ化

print(rec(0, n))

Submission status: Time Limit Exceeded

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

Submission status: Time Limit Exceeded

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

#dp[l][r] = [l, r)区間のスライムを
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    else:
        res = float("inf")
        if (r - l) == 1:
            dp[l][r] = 0
            return dp[l][r]
        for k in range(l, r):
            if k == l or k == r:
                continue
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
def f(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi=dp[i]
        for j in range(i + 1, n):
            k = []
            s += a[j]
            for d in range(i, j):
                k += [dpi[d] + dp[d + 1][j]]
            dp[i][j] = min(k) + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = tuple(map(int, input().split()))

dp = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
    s = a[i]
    for j in range(i + 1, n):
        k = []
        s += a[j]
        for d in range(i, j):
            k += [dp[i][d] + dp[d + 1][j]]
        dp[i][j] = min(k) + s
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
def cost(a):
    la = len(a)
    if la == 1:
        return 0
    if la == 2:
        return a[0] + a[1]
    if a in memo:
        return memo[a]
    re = []
    for i in range(1, la):
        re += [cost(a[:i]) + cost(a[i:]) + sum(a)]
    re = min(re)
    memo[a] = re
    return re


memo = {}
n = int(input())
a = tuple(map(int, input().split()))
print(cost(a))

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
maxa = pow(10,18)
arr = list(map(int,input().split()))

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

pref = [0 for i in range(n)]
pref[0] = arr[0]
for i in range(1,n):
    pref[i] = pref[i-1] + arr[i]
#print(pref)
for l in range(2,n+1):
    for i in range(n-l+1):
        j = i+l-1
        dp[i][j] = maxa
        for k in range(i,j):
            if(i-1>=0):
                suma = pref[j] - pref[i-1]
            else:
                suma = pref[j]
                
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+ suma )
            #print(dp[i][j])

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

Submission status: Time Limit Exceeded

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

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

def calc_cost(left, right):
    if dp[left][right] >= 0:
        return dp[left][right]
    min_ = min(calc_cost(left, i) + calc_cost(i+1, right) for i in range(left, right))
    dp[left][right] = cumsum[right+1]-cumsum[left] + min_
    return dp[left][right]

print(calc_cost(0,n-1))

Submission status: Time Limit Exceeded

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

INF = 10 ** 20

dp = [[0 for _ in range(n)] for _ in range(n)]

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

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        temp = INF
        for i in range(k):
            temp = min(temp, dp[x][x+i] + dp[x+i+1][y] + sum(a[x:y+1]))
        dp[x][y] = temp

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

Submission status: Time Limit Exceeded

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

INF = 10 ** 20

dp = [[INF for _ in range(n)] for _ in range(n)]

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

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        for i in range(k):
            dp[x][y] = min(dp[x][y], dp[x][x+i] + dp[x+i+1][y] + sum(a[x:y+1]))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from functools import lru_cache
from itertools import accumulate as accum
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f(l, r):
    if l == r:
        return(0)
    cost = float('inf')
    for x in range(l, r):
        cost_ = f(l, x) + f(x + 1, r)
        if cost_ < cost:
            cost = cost_
    return(cost + acsum[r] - acsum[l - 1])

n = int(input()) # 2 <= n <= 400
acsum = list(accum(map(int, input().split()))) + [0]
print(f(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from functools import lru_cache
from itertools import accumulate as accum
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f(l, r):
    if l == r:
        return(0)
    return(min(f(l, x) + f(x + 1, r) for x in range(l, r)) \
        + acsum[r] - acsum[l - 1])

n = int(input()) # 2 <= n <= 400
acsum = list(accum(map(int, input().split()))) + [0]
print(f(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
def mcm(p,n):
    cost=[[0 for x in xrange(n)] for x in xrange(n)]
    new=[[0 for x in xrange(n)] for x in xrange(n)]
    for i in xrange(0,n):
        new[i][i]=p[i]
        cost[i][i]=0
    for l in xrange(2,n+1):
#        print "len",l
        for i in xrange(0,n-l+1):
            j=i+l-1
            if l==2:
                cost[i][j]=p[i]+p[j]
            else:
                cost[i][j]=9*(10**9)
            new[i][j]=new[i][j-1]+p[j]
#            print p[i:j+1]
            for k in xrange(i,j):
#                print p[i:k+1],p[k+1:j+1]
#                print new[i][k],new[k+1][j],cost[i][k],cost[k+1][j]
                co=(new[i][k]+new[k+1][j])+cost[i][k]+cost[k+1][j]
#                print "cost",co,cost[i][j]
                if co<cost[i][j]:
                    cost[i][j]=co
#                print"-----"
#        print"==================="
#    print cost
#    print new
    print cost[0][-1]

n=int(input())
l=list(map(int,raw_input().split()))
le=len(l)
mcm(l,le)

Submission status: Time Limit Exceeded

Solution code:
# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035


def div_cost(left, right):
    # 区間[left, right]が一匹にまとまっているとき、それを分解するために必要な最小コスト
    if bl_calculated[left][right]:
        return memo[left][right]
    bl_calculated[left][right] = True
    if left == right:
        memo[left][right] = 0
        return memo[left][right]
    divided_to_alone_cost = INF
    # divided_to_alone_cost: 区間[left, right]を分解してできた2つの区間それぞれをaの各要素まで分解し切るのに必要なコスト
    for mid in range(left, right):
        divided_to_alone_cost = min(divided_to_alone_cost, div_cost(left, mid) + div_cost(mid + 1, right))
    memo[left][right] = divided_to_alone_cost + (c_sum[right] - c_sum[left - 1])
    # (c_sum[right] - c_sum[left - 1]): 区間[left, right]を分解するのにかかるコスト
    return memo[left][right]


INF = float('inf')

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

c_sum = [0]
for aa in a:
    c_sum.append(c_sum[-1] + aa)
# 累積和c_sum

memo = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
# memo[left][right] = (区間[left, right]に相当するスライムが一匹にまとまっているとき、それを分解するために必要な最小コスト)

bl_calculated = [[False for _ in range(N + 1)] for _ in range(N + 1)]
# memo[left][right]に最小コストが代入済かどうかのBoolean

print(div_cost(1, N))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo=[[-1 for i in range(401)]for i in range(401)]
def split_slime(l,r):
    if l+1==r:
        return 0
    if memo[l][r]!=-1:
        return memo[l][r]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[l][r]=mn
    return memo[l][r]
print(split_slime(0,n))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo={}
def split_slime(l,r):
    if l+1==r:
        return 0
    if (l,r) in memo:
        return memo[(l,r)]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[(l,r)]=mn
    return memo[(l,r)]
print(split_slime(0,n))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import itertools
sys.setrecursionlimit(1000000)
n=int(input())
a=list(map(int,input().split()))
d=[0]+list(itertools.accumulate(a))
memo={}
ans=0
def split_slime(l,r):
    global ans
    if (l,r) in memo:
        return memo[(l,r)]
    if l+1==r:
        return 0
    mn=10**18
    m=0
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
            m=i
    memo[(l,r)]=mn
    return memo[(l,r)]
print(split_slime(0,n))

Submission status: Time Limit Exceeded

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

INF = float('inf')
dp = [[INF] * (n+1) for _ in range(n+1)]

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

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

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + acum[j] - acum[i])

print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[float("inf")]*(N-i+1) for i in range(N+1)]
    dp[1] = [0] * N
    for i in range(2, N+1):
        for j in range(N-i+1):
            for k in range(1, i):
                dp[i][j] = min(dp[k][j] + dp[i-k][j+k] +
                               sum(A[j:j+i]), dp[i][j])
    print(dp[N][0])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

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

for d in range(1, N):
    for l in range(N-d):
        r = l + d
        if d == 0:
            dp[l][r] = A[l]
            
        else:
            dp[l][r] = 10**20
            for m in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + sum(A[l:r+1]))
    

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp = [[0]*n for _ in range(n)]
for i in range(1,n):
    for j in range(n-i):
        tmp = 1234567890123
        su = 0
        for k in range(j,j+i):
            tmp = min(tmp,dp[j][k]+dp[k+1][j+i])
            su += a[k]
        su += a[i+j]
        dp[j][j+i] = su + tmp
print(dp[0][n-1])

Submission status: Time Limit Exceeded

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

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

for i in range(1,n):
    for j in range(n-i):
        tmp = 1234567890123
        sum = 0
        for k in range(j,j+i):
            tmp = min(tmp,dp[j][k]+dp[k+1][j+i])
            sum += a[k]
        sum += a[i+j]
        dp[j][j+i] = sum + tmp
print(dp[0][n-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+a_acc[r]-a_acc[l]
            return dp[l][r-1]


dfs(0, N)
#print("ans->", dp[0][-1])
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict, deque

dp = defaultdict(lambda: -1)

q = deque([])
q.append((A, 0))

inf = float("inf")

ans = inf
while q:
    t, cost = q.popleft()
    if len(t) == 0:
        ans = min(ans, cost)
        continue

    if len(t) == 1:
        ans = min(ans, cost + t[0])
        continue

    tpl = t
    for i in range(len(tpl) - 1):
        if not (tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], tpl[i] + tpl[i + 1]) in q:
            q.append((tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], cost + tpl[i] + tpl[i + 1]))

print(ans - sum(A))
exit(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict
dp = defaultdict(lambda : -1)

def dfs(tpl):
    if dp[tpl] != -1:
        return dp[tpl]
    if len(tpl) == 0:
        return 0
    if len(tpl) == 1:
        dp[tpl] = tpl[0]
        return tpl[0]

    lst_candidates = []
    now_cost = []
    for i in range(len(tpl)-1):
        # print("i: ", i )
        lst_candidates.append (   tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ]   )
        now_cost.append ( tpl[i] + tpl[i+1] ) 

    total_cost = []
    for i in range(len(now_cost)):
        total_cost.append ( now_cost [i] + dfs(lst_candidates[i]))

    # print("totla_cost: ", total_cost)
    # print("lst_candidates: ", lst_candidates)
    res = min(total_cost)
    dp[tpl] = res

    return res

print(dfs(A) - sum(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict
dp = defaultdict(lambda : -1)

def dfs(tpl):
    if dp[tpl] != -1:
        return dp[tpl]
    if len(tpl) == 0:
        return 0
    if len(tpl) == 1:
        dp[tpl] = tpl[0]
        return tpl[0]

    lst_candidates = []
    now_cost = []
    for i in range(len(tpl)-1):
        # print("i: ", i )
        lst_candidates.append (   tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ]   )
        now_cost.append ( tpl[i] + tpl[i+1] ) 

    total_cost = []
    for i in range(len(now_cost)):
        total_cost.append ( now_cost [i] + dfs(lst_candidates[i]))

    # print("totla_cost: ", total_cost)
    # print("lst_candidates: ", lst_candidates)
    res = min(total_cost)
    dp[tpl] = res

    return res

print(dfs(A) - sum(A))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
　　　https://atcoder.jp/contests/dp/submissions/3970847
・メモ化再帰
・累積和
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# 累積和
sm = [0] * (N+1)
for i in range(N):
    sm[i+1] = sm[i] + aN[i]

memo = list2d(N+1, N+1, INF)
def rec(l, r):

    if memo[l][r] != INF: 
        return memo[l][r]
    if l == r:
        return 0
    mn = INF
    # 開区間にした
    for m in range(l, r):
        mn = min(mn, rec(l, m) + rec(m+1, r))
    # この先切った分の最小値に、今回のlとrを合体させる分を足す
    memo[l][r] = mn + (sm[r] - sm[l-1])
    return memo[l][r]

print(rec(1, N))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
dp = [[0] * (n + 1) for _ in range(n)]
for l, aa in enumerate(zip(aaa, aaa[1:])):
    dp[l][l + 2] = sum(aa)
for w in range(3, n + 1):
    for l in range(n - w + 1):
        r = l + w
        c = acc[r] - acc[l]
        dp[l][r] = min(dp[l][m] + dp[m][r] + c for m in range(l + 1, r))
print(dp[0][n])

Submission status: Time Limit Exceeded

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

DPLIST=[[None]*N for i in range(N)]

SUM=[0]
for i in range(N):
    DPLIST[i][i]=0
    SUM.append(SUM[-1]+A[i])

for i in range(1,N):
    for j in range(i,N):

        ANS=float("inf")

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

            if ANS>DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]:
                ANS=DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]
        
        DPLIST[j-i][j]=ANS

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

Submission status: Time Limit Exceeded

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

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
cost = [0]
for p in a:
	cost.append(cost[-1] + p)
def get_cost(l, r):
	return cost[r+1] - cost[l]

dp = [[float("inf") for _ in range(n)] for _ in range(n)]
for i, p in enumerate(a):
	dp[i][i] = 0

for g in range(1, n):
	for l in range(n-g):
		r = l + g
		for m in range(l, r):
			dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + get_cost(l, r))

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

Submission status: Accepted

Solution code:
from itertools import accumulate
INF=1001001001001
n=int(input())
a=list(map(int,input().split()))
dp=[[INF for i in range(n+1)] for j in range(n+1)]
wa=[0]+list(accumulate(a))
for i in range(n):
  dp[i][i+1]=0
for gap in range(2,n+1):
  for l in range(n-gap+1):
    r=l+gap
    dp[l][r]=wa[r]-wa[l]+min(dp[l][k]+dp[k][r] for k in range(l+1,r))
print(dp[0][n])

Submission status: Accepted

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

DP = [[(0, float('inf'))] * (N+1) for _ in range(N)]

for num in range(1, N+1):
    for start in range(N):
        end = start + num
        if end > N:
            break
        if num == 1:
            DP[start][end] = (A[start], 0) # （大きさ、コスト）
            continue
        for i in range(start + 1, end):
            tmp = DP[start][i][0] + DP[start][i][1] + DP[i][end][0] + DP[i][end][1]
            large = DP[start][i][0] + DP[i][end][0]
            if DP[start][end][1] > tmp:
                DP[start][end] = (large, tmp)
print(DP[0][N][1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
import math

def main():
  input=sys.stdin.readline
  n=int(input())
  A=list(map(int,input().split()))
  dp=[[math.inf]*n for _ in range(n)]
  for i in range(n):
    dp[i][i]=0
  #print(*dp,sep="\n")
  accA=list(accumulate([0]+A))
  #print(accA)
  for L in reversed(range(n)):
    dpL=dp[L]
    for R in range(L+1,n):
      dpL[R]=min([dpL[k-1]+dp[k][R] for k in range(L+1,R+1)])+accA[R+1]-accA[L]
  #print(dp)
  print(dp[0][-1])
main()

Submission status: Accepted

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

dp = [[0 for i in range(N)] for i in range(N)]
res = 0

def f(l, r):
  if 0 < dp[l][r]:
    return dp[l][r]
  if l == r:
    return 0
  fans = float('inf')
  for m in range(r)[l:]:
    fans = min(fans, f(l, m)+f(m+1, r))
  dp[l][r] = fans + sum(A[l:r+1])
  return dp[l][r]
  
print(f(0,N-1))

Submission status: Accepted

Solution code:
from itertools import accumulate

INF = 10**18

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

S = [0] + list(accumulate(A))

dp = [[INF for j in range(N + 1)] for i in range(N + 1)]

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

print(dp[0][N])

Submission status: Accepted

Solution code:
INF = 10**18


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    dp = [[INF]*(N+1) for _ in range(N)]
    cost = [[INF]*(N+1) for _ in range(N)]

    for i in range(N):
        dp[i][i+1] = A[i]
        cost[i][i+1] = 0

    for w in range(2, N+1):
        for le in range(N-w+1):
            ri = le + w
            for i in range(le+1, ri):
                if dp[le][ri] >= dp[le][i] + dp[i][ri]:
                    dp[le][ri] = dp[le][i] + dp[i][ri]
                    cost[le][ri] = min(cost[le][ri],
                                       cost[le][i] + cost[i][ri] + dp[le][ri])

    print(cost[0][N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
C=[0]
for i in range(N):
  C.append(C[i]+A[i])
INF=10**18
DP=[[INF]*N for i in range(N)]
def f(l,r):
  if l==r:
    return 0
  if DP[l][r]!=INF:
    return DP[l][r]
  for i in range(l+1,r+1):
    DP[l][r]=min(DP[l][r],f(l,i-1)+f(i,r)+C[r+1]-C[l])
  return DP[l][r]

print(f(0,N-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)

'''
DPじゃなくて貪欲に小さい方からくっつけるのじゃだめ？←隣り合うという制約が入れられない

sum a_i から をaiに分解するイメージ
dp[i,j] ... コストの最小. A[i:j]を合体させたとき

更新式
dp[i,j] = min(dp[i,i+1] + dp[i+1,j],
              dp[i,i+2] + dp[i+2,j],...
              ) + sum(A[i,j])

dp[i,i+1]=0かな？
'''


N = a_int()
A = ints()
A_accum = zeros(N + 1)
A_accum[1:] = np.cumsum(A)
dp = full((N + 1, N + 1), -1)
dp[np.arange(N), np.arange(N) + 1] = 0

from numba import njit


@njit('(i8,i8,i8[:,:],i8[:])', cache=True)
def dfs(i, j, dp, A_accum):
    if dp[i, j] != -1:
        return dp[i, j]
    mi = 10**14
    for k in range(i + 1, j):
        mi = min(mi, dfs(i, k, dp, A_accum) + dfs(k, j, dp, A_accum))
    dp[i, j] = mi + A_accum[j] - A_accum[i]
    return dp[i, j]


print(dfs(0, N, dp, A_accum))