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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
最後の2つを決める：[0,x) [x,N)
小問題2つに分割できる。
全ての連続区間を計算すればよい
"""

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

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

dp = np.zeros((N,N+1), dtype=np.int64)
for size in range(2,N+1):
    for L in range(N-size+1):
        R = L + size
        dp[L,R] = (dp[L,L+1:R] + dp[L+1:R,R]).min() + Acum[L,R]

answer = dp[0,N]
print(answer)

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

dp = [[0]*(N+1) for i in range(N+1)]
data = [[0]*(N+1) for i in range(N+1)] # data[i][j] = sum(a[i:j])
for i in range(N):
  data[i][i+1] = a[i]
for i in range(N+1):
  for j in range(N+1):
    if i+j <= N:
      data[j][i+j] = sum(a[j:i+j])
    else:
      break

for i in range(2,N+1):
  for j in range(N+1):
    if i+j <= N:
      tmp = MAX_INT
      for k in range(1,i):
        tmp = min(tmp,dp[j][k+j] + dp[k+j][i+j])
      dp[j][i+j] = tmp + data[j][i+j]
    else:
      break

#print(data)
#print(dp)
print(dp[0][N])

Submission status: Accepted

Solution code:
# @author 

import sys

class NSlimes:
    def solve(self):
        n = int(input())
        a = [None] + [int(_) for _ in input().split()]

        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            dp[i][i] = 0
        for i in range(n + 1, 0, -1):
            for j in range(1, n + 1):
                s = sum(a[p] for p in range(i, j + 1))
                for k in range(i, j):
                    dp[i][j] = min(dp[i][k] + dp[k + 1][j] + s, dp[i][j])

        print(dp[1][n])


        # Greedy, not working

        # b = a[:]
        # ans = 0
        # for i in range(n - 1):
        #     idx = -1
        #     mn = float('inf')
        #     for j in range(n - 1 - i):
        #         if b[j] + b[j + 1] < mn:
        #             mn = b[j] + b[j + 1]
        #             idx = j
        #     assert(idx != -1)
        #     b[idx] += b[idx + 1]
        #     ans += b[idx]
        #     del b[idx + 1]
        # assert(len(b) == 1)
        # print(ans)

solver = NSlimes()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

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

DP = [[[0] * 2 for _ in range(N)] for _ in range(N + 1)]
for i in range(N):
  DP[1][i] = [a[i], 0]

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

print(DP[N][0][1])

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().strip().split(" ")))
dp=[[10**20]*len(A)  for i in range(0,len(A)+1)]
##dp[length][start_position]
pre=[]
temp=0
for i in range(len(A)):
    temp+=A[i]
    pre+=[temp]
length=1
for i in range(len(A)):
    dp[length][i]=0

for L in range(2,len(A)+1):
    for start in range(0,len(A)-L+1):
        for j in range(start+1,start+L):
            if start>0:
                dp[L][start]=min(dp[j-start][start]+dp[L-j+start][j]+pre[start+L-1]-pre[start-1],dp[L][start])
            else:
                dp[L][start]=min(dp[j-start][start]+dp[L-j+start][j]+pre[start+L-1],dp[L][start])
print(dp[len(A)][0])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
intINF = int(1e15)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
a = LI()

dp = [[intINF]*(N+1) for i in range(N+1)]
acc = [0]*(N+1)
for i in range(N):
    acc[i+1] = acc[i] + a[i]

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

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

print(dp[0][N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))
dp = [[0] * (N + 1) for _ in range(N + 1)]
#dp[i][j]: 半開区間[i,j)のスライムを結合した時の最小のコスト
sum = [0] * (N + 1) #累積和
inf = float('inf')

for i in range(N):
	sum[i + 1] = sum[i] + a[i]
	
for c in range(2, N + 1):
	for i in range(N - c + 1):
		ans = inf
		for k in range(1, c):
			tmp = dp[i][i + k] + dp[i + k][i + c] + sum[i + c] - sum[i]
			if tmp < ans:
				ans = tmp
				
		dp[i][i + c] = ans
		
print(dp[0][N])

Submission status: Accepted

Solution code:
inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

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

accmulate(A)

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

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

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

ans = dp[0][N]
print(ans)

Submission status: Accepted

Solution code:
import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = float('inf')
N = int(input())
a = list(map(int,input().split()))
cum = [0]*(N+1)
for i in range(N):
    cum[i] = cum[i-1]+a[i]
dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0

def cal(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        res = INF
        for k in range(i,j):
            res = min(res,cal(i,k)+cal(k+1,j)+cum[j]-cum[i-1])
        dp[i][j] = res
        return res

print(cal(0,N-1))

Submission status: Accepted

Solution code:
def calcdp(i,j):
    global dp, A, BIG_INT
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    if i + 1== j:
        dp[i][j] = 0
        return dp[i][j]
    
    elif i + 2== j:
        dp[i][j] = A[i] + A[i + 1]
        return dp[i][j]
    
    else:
        m = BIG_INT
        for k in range(i + 1, j):
            m = min(calcdp(i, k) + calcdp(k, j), m)
        m += sum(A[i:j])
        dp[i][j] = m
        return dp[i][j]

    
BIG_INT = 10**30
N = int(input())
A = [int(x) for x in input().split()]
dp = [[-1] * (N + 1) for _ in range(N)] 

print(calcdp(0, N))

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
SA = list(accumulate(A)) + [0]
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(2, N+1):
    for j in range(N-i+1):
        dp[i][j] = SA[j+i-1] - SA[j-1] + min(dp[k][j] + dp[i-k][j+k] for k in range(1, i))
print(dp[-1][0])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n=int(input())
aa = [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate

acc = list(accumulate([0]+aa))

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

def dp(r,l):
    if memo[r][l] > 0:
        return memo[r][l]
    if r-l==1:
        memo[r][l] = 0
        return 0
    res=0
    res = min([dp(c,l) + dp(r,c) for c in range(l+1,r)])
    res += acc[r]- acc[l]

    memo[r][l] = res
    return res

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[float("inf")] * n for _ in range(n)]
s = [0] * (n + 1)

for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i - 1]
for i in range(n):
    dp[i][i] = 0

for w in range(1, n):
    for i in range(n - w):
        for j in range(i, i + w):
            dp[i][i + w] = min(dp[i][i + w], dp[i][j] + dp[j + 1][i + w] + s[i + w + 1] - s[i])
print(dp[0][n - 1])

Submission status: Accepted

Solution code:
from math import isinf
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 not isinf(dp[l][r]):
        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: Accepted

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, infnum):
    if dp[l][r] != infnum:
        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, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n, float("inf"))
print(dp[0][n])

Submission status: Accepted

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[-1]*(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] != -1:
        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: Accepted

Solution code:
def f(n, a):
    inf = float("inf")
    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):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


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

Submission status: Accepted

Solution code:
def f(n, a):
    inf = float("inf")
    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):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


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

Submission status: Accepted

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f2(n, a):
    acsum = list(accum(a)) + [0]
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        if i + 1 != n:
            dp[i][i + 1] = a[i] + a[i + 1]
    for i in range(n - 3, -1, -1):
        for j in range(i + 2, n):
            c = float('inf')
            dpi = dp[i]
            for x in range(i, j):
                c_ = dpi[x] + dp[x + 1][j]
                if c_ < c:
                    c = c_
            dpi[j] = c + acsum[j] - acsum[i - 1]
    return(dp[0][n - 1])

n = int(input()) # 2 <= n <= 400
a = list(map(int, input().split()))
print(f2(n, a))

Submission status: Accepted

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

INF = 10 ** 20

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

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


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] + s[y+1] - s[x])
        dp[x][y] = temp

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from itertools import accumulate
n=int(input())
A=[0]+list(accumulate(map(int,input().split())))
DP=[[0]*n for _ in range(n)]
for d in range(1,n):
    for i in range(n-d):
        j=i+d
        tmp=float('inf')
        for k in range(i,j):
            tmp=min(tmp,DP[i][k]+DP[k+1][j])
        DP[i][j]=tmp+A[j+1]-A[i]
print(DP[0][n-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))

#b[q+1]-b[p] = a[p]+...a[q]
b = [0]*(n+1)
for i in range(n):
    b[i+1] = b[i]+a[i]

#dp[i][j] : i~j までをまとめるコストの最小値
dp = [[0]*n for i in range(n)]
for j in range(1,n):
    for i in range(n-j):
        
        mi = float("inf")
        for k in range(i,i+j):
            mi = min(mi,dp[i][k]+dp[k+1][i+j])
        dp[i][i+j] = mi+b[i+j+1]-b[i]

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

Submission status: Accepted

Solution code:
def get_cost(l, r):
    # 区間[l, r]の結合を分解し切るコスト
    if memo[l][r] < INF: return memo[l][r]
    if r == l: return 0

    t = INF
    for m in range(l, r):
        t = min(t, get_cost(l, m) + get_cost(m + 1, r))
    memo[l][r] = t + (c_sum[r] - c_sum[l - 1])
    return memo[l][r]


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

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

INF = float('inf')

memo = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
# 区間[l, r]の結合を分解し切るコスト

print(get_cost(1, N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
from __future__ import division, print_function

import os
import sys
from atexit import register
from io import BytesIO

range = xrange

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
a = [float(i) for i in input().split()]

pref_sums = [0.0] * (n + 1)
for i in range(n):
    pref_sums[i + 1] = pref_sums[i] + a[i]

dp = [[0.0] * n for _ in range(n)]


def solve(start, end):
    if (dp[start][end] == 0.0) and (start != end):
        dp[start][end] = min(
            solve(start, i) + solve(i + 1, end) + pref_sums[end + 1] - pref_sums[start] for i in range(start, end))
    return dp[start][end]


print(int(solve(0, n - 1)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
from __future__ import division, print_function

import os
import sys
from atexit import register
from io import BytesIO

range = xrange

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
a = [int(i) for i in input().split()]

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

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


def solve(start, end):
    if (dp[start][end] == 0) and (start != end):
        dp[start][end] = min(pref_sums[i + 1] - pref_sums[start] + pref_sums[end + 1] - pref_sums[i + 1] +
                             solve(start, i) + solve(i + 1, end) for i in range(start, end))
    return dp[start][end]


print(solve(0, n - 1))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [[0] * (n - i) for i in range(n)]

csum_ = [0]
for a in A:
    csum_.append(csum_[-1] + a)

def csum(i, j): #[i, j)
    return csum_[j] - csum_[i]

for i in range(1, n):
    for j in range(n-i):
        if i > 1:
            DP[i][j] = min(DP[k][j] + DP[i-k-1][j+k+1] for k in range(0, i))

        DP[i][j] += csum(j, j + i + 1)

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

Submission status: Accepted

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

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

# 累積和は0を含んだ半開区間（1-indexed)でかく
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

# 区間dp
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: Accepted

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: Accepted

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [0]
for a in A:
    B.append(B[-1]+a)

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] + B[r+1]-B[l])
    
print(dp[0][N-1])

Submission status: Accepted

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(0)]*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]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
ans = int(dp[0][-1])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

a_acc = [0] + list(accumulate(a_list))

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

for d in range(2, N + 1):
    for l in range(N + 1 - d):
        r = l + d
        tmp = float("inf")
        for m in range(l+1, r):
            tmp = min(tmp, dp[l][m] + dp[m][r])
        dp[l][r] = tmp + a_acc[r] - a_acc[l]

print(dp[0][N])

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline

INF = float('inf')

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

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

prefix = [0]+ list(accumulate(a))

for i in range(1,N):
    for j in range(0,N-i):
        temp = INF
        for k in range(i):
            temp = min(temp,cost[j][j+k] + cost[j+k+1][j+i])
        cost[j][j+i] = temp + prefix[j+i+1] - prefix[j]


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

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline

INF = float('inf')

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

cost = [[0]*N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0
prefix = [0]+ list(accumulate(a))

for i in range(1,N):
    for j in range(0,N-i):
        temp = INF
        for k in range(i):
            temp = min(temp,cost[j][j+k] + cost[j+k+1][j+i])
        cost[j][j+i] = temp + prefix[j+i+1] - prefix[j]


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

Submission status: Accepted

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

from itertools import accumulate
Accum = list(accumulate([0] + A))

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

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))

Submission status: Accepted

Solution code:


n = input()
a = map(int, raw_input().split())
oo = sum(a) * n
cumul = [0] * (n + 1)
for i in range(n):
    cumul[i + 1] = cumul[i] + a[i]

dp = [[oo] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
for i in range(1, n):
    for j in range(n - i):
        k = j + i
        for l in range(j, k):
            dp[j][k] = min(dp[j][k], dp[j][l] + dp[l + 1][k])
        dp[j][k] += cumul[k + 1] - cumul[j]
print(dp[0][n - 1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    l = n + 1

    t = [[0]*n for _ in range(n)]
    w = [0] * l
    for i in range(n):
        w[i+1] = w[i] + a[i]

    for i in range(n-2,-1,-1):
        z = t[i]
        y = t[i+1]
        c = w[i]
        for j in range(i+1,n):
            b = inf
            for k in range(i,j):
                e = z[k] + t[k+1][j]
                if b > e:
                    b = e
            t[i][j] = b + w[j+1] - c

    return t[0][-1]


print(main())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

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

SUM=[0]
for i in range(N):
    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: Accepted

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

INF = 10**18
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]
dp = [[0]*(N+1) for i in range(N+1)]
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)) + S[i+k] - S[i]
print(dp[0][N])

Submission status: Accepted

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)
print(dp[0][n-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
A = list(map(int,input().split()))
C = [0]
for a in A:
    C.append(C[-1] + a)

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

def rec(l,r):
    if dp[l][r]: return dp[l][r]
    if l == r: return 0
    if r-l == 1: return A[l] + A[r]
    ret = C[r+1] - C[l]
    tmp = min(rec(l+1,r), rec(l,r-1))
    for i in range(r-l-2):
        tmp = min(tmp, rec(l,l+i+1) + rec(l+i+2,r))
    ret += tmp
    dp[l][r] = ret
    return ret

print(rec(0,N-1))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[float("inf")] * (n+1) for i in range(n+1)]
rui = [0] * (n+1)
for i in range(n):
  rui[i+1] = rui[i] + a[i]
for i in range(n+1):
  for j in [-1,0,1]:
    if i + j > n:
      continue
    if i+j < 0:
      continue
    dp[i][i+j] = 0
for j in range(2,n+1):
  for i in range(n+1-j):
    for k in range(j):
      dp[i][i+j] = min(dp[i][i+k] +dp[i+k][i+j] + rui[i+j]-rui[i],dp[i][i+j])
print(dp[0][n])

Submission status: Accepted

Solution code:
from itertools import accumulate
N=int(input())
a=[int(i) for i in input().split()]
dp=[[float("inf")]*(N+1) for i in range(N+1)]
S=[0]+list(accumulate(a))
for i in range(N):
  dp[i][i+1]=0
for d in range(2,N+1):
  for i in range(N+1-d):
    for k in range(i+1,i+d):
      dp[i][i+d]=min(dp[i][i+d],dp[i][k]+dp[k][i+d]+S[i+d]-S[i])
print(dp[0][N])