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:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


n=int(inp())
ar=lis()
inf=float("inf")
dp=[[inf for i in range(n+5)] for _ in range(n+5)]
for i in range(n):
    dp[i][i]=0
prefix=[0,ar[0]]
for i in range(1,n):
    prefix.append(prefix[i]+ar[i])
for i  in range(n-1,-1,-1):
    for j in range(i+1,n):
        for k in range(0,j-i):
            dp[i][j]=min(dp[i][j],(dp[i][i+k]+dp[i+k+1][j])+prefix[j+1]-prefix[i])

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

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

N = int(input())
slimes = np.array(list(map(int, input().split())), dtype='int64')
csum_slimes = [0]
for i in range(N):
    csum_slimes.append(csum_slimes[-1]+slimes[i])
csum_slimes = np.array(csum_slimes, dtype='int64')

dpt = np.full((N, N), -1, dtype='int64')

@njit(cache=True)
def get_min_cost(l, r, slimes, dpt, csum_slimes):
    if dpt[l][r] != -1:
        return dpt[l][r]
    if l == r:
        return 0
    min_cost = 10**18
    for m in range(l, r):
        min_cost = min(min_cost, get_min_cost(l,m,slimes,dpt,csum_slimes)+get_min_cost(m+1,r,slimes,dpt,csum_slimes)+csum_slimes[r+1]-csum_slimes[l])
    dpt[l][r] = min_cost
    return min_cost
    

print(get_min_cost(0, N-1, slimes, dpt, csum_slimes))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)

s=[0]

dp=np.array([[-1 for i in range(N)] for _ in range(N)],dtype=np.int64)

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

s=np.array(s,dtype=np.int64)
for i in range(N):
    dp[i][i]=0

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

print(calc(0,N-1,dp,s))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
dp=[[-1]*n for i in range(n)]
acc=list(accumulate(lis))
for i in range(n):
    dp[i][i]=0
def memo(x,y):
    if dp[x][y]>=0:
        return dp[x][y]
    res=inf
    for i in range(x,y):#左側区間の右端
        if x==0:
            if acc[y]+memo(x,i)+memo(i+1,y)<res:
                res=acc[y]+memo(x,i)+memo(i+1,y)
        else:
            if acc[y]-acc[x-1]+memo(x,i)+memo(i+1,y)<res:
                res=acc[y]-acc[x-1]+memo(x,i)+memo(i+1,y)
    dp[x][y]=res
    return res
        
for i in range(n):
    for j in range(i,n):
        memo(i,j)
#print(dp)
print(dp[0][-1])

Submission status: Accepted

Solution code:
n=int(input())
A = list(map(int,input().split()))
from itertools import accumulate
S = [0] + list(accumulate(A))
dp = [[0]*(n+1) for _ in range(n+1)]
for d in range(2,n+1):
    for i in range(n-d+1):
        j = i+d
# for i in range(n+1):
#     for j in range(i+1,n+1):
        val = float('inf')
        for k in range(i+1,j):
            val = min(val,dp[i][k]+dp[k][j])
        dp[i][j] += S[j]-S[i] + val
print(dp[0][-1])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret
N = I()
A = IL()
ACC = ACC1(A)

dp = [[INF for r in range(N)] for l in range(N)]

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

Submission status: Accepted

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

sumx=[0]+list(itertools.accumulate(a))

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

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

print(dp[0][-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
acc = [0] + list(accumulate(A))
dp = [[0] * n for _ in range(n)]

def f(l, r):
    if dp[l][r] or l == r:
        return dp[l][r]
    m = INF
    for i in range(l, r):
        m = min(m, f(l, i) + f(i + 1, r) + acc[r + 1] - acc[l])
    dp[l][r] = m
    return m

print(f(0, n-1))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
acc = [0] + list(accumulate(A))
dp = [[0] * n for _ in range(n)]

def f(l, r):
    if dp[l][r]:
        return dp[l][r]
    if l == r:
        return 0
    m = INF
    for i in range(l, r):
        m = min(m, f(l, i) + f(i + 1, r) + acc[r + 1] - acc[l])
    dp[l][r] = m
    return m

print(f(0, n-1))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split())) + [0]
INF = float("inf")

sum_a = list(itertools.accumulate(a))

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

for k in range(2,N+1):
    for l in range(1,N-k+2):
        r = l + k
        for i in range(r-l-1):
            w1 = sum_a[l+i] - sum_a[l-1]
            w2 = sum_a[r-1] - sum_a[l+i]
            dp[l][r] = min(dp[l][r], dp[l][l+i+1] + dp[l+i+1][r] + w1 + w2)

print(dp[1][N+1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=list(map(int,input().split()))
dp=[[10**18]*(n) for _ in range(n)]
flag=[[0]*n for _ in range(n)]
accum=[a[0]]
for i in range(1,n):
    accum.append(accum[-1]+a[i])
accum=[0]+accum
def f(l,r):
    if l==r:
        return 0
    if flag[l][r]:
        return dp[l][r]
    flag[l][r]=1
    ret=10**18
    for i in range(l,r):
        ret=min(ret,f(l,i)+f(i+1,r))
    dp[l][r]=ret+accum[r+1]-accum[l]
    return dp[l][r]
f(0,n-1)
print(dp[0][n-1])

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*n for _ in range(n)]
dp1 = [[0]*n for _ in range(n)]
for i in range(n-1):
    dp1[i][i] = arr[i]
    dp[i][i+1] = arr[i]+arr[i+1]
    dp1[i][i+1] = arr[i]+arr[i+1]
dp1[-1][-1] = arr[-1]
for i in range(n-3,-1,-1):
    for j in range(i+2,n):
        dp[i][j] = 10**20
        for k in range(j-1,i-1,-1):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp1[i][k]+dp[k+1][j]+dp1[k+1][j])
        dp1[i][j] = dp1[i][j-1]+arr[j]
print(dp[0][-1])

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  cum = [0]+list(accumulate(A))
  dp = [[float('inf')]*N for _ in range(N)]
  for i in range(N):
    dp[i][i] = 0
  for i in range(N-1):
    dp[i][i+1] = A[i]+A[i+1]
  for k in range(2,N):
    for i in range(N):
      j = i+k
      if j>N-1:
        break
      for l in range(i,j):
        dp[i][j] = min(dp[i][j],dp[i][l]+dp[l+1][j])
      dp[i][j] += cum[j+1]-cum[i]
  ans = dp[0][-1]
  return ans
print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
dp=[[[10**18,10**18] for _ in range(n)] for _ in range(n)]
for i in range(n):
  dp[i][i][0]=arr[i]
  dp[i][i][1]=0
for i in range(1,n):
  for j in range(n-i):
    for k in range(i):
      if dp[j][j+i][1]>dp[j][j+k][0]+dp[j+k+1][j+i][0]+dp[j][j+k][1]+dp[j+k+1][j+i][1]:
        dp[j][j+i][1]=dp[j][j+k][0]+dp[j+k+1][j+i][0]+dp[j][j+k][1]+dp[j+k+1][j+i][1]
        dp[j][j+i][0]=dp[j][j+k][0]+dp[j+k+1][j+i][0]
print(dp[0][n-1][1])

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()
    a.append(INF)

    # dp[i][j] : aのi個めからj-1個めまでを合体した時の最小値　a[i,j)
    dp = [[0 if _ == __ else INF for _ in range(n + 1)] for __ in range(n + 1)]

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

    for d in range(2, n + 1):
        for i in range(n + 1 - d):
            j = i + d
            total = sum(a[i:j])
            for k in range(1, d):
                dp[i][j] = min(dp[i][j], dp[i][i + k] + dp[i + k][j] + total)

    print(dp[0][n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

arr = list(map(int, input().split()))


sums = [0 for i in range(len(arr))]

sums[0] = arr[0]

for i in range(1, len(sums)):
    sums[i] = sums[i-1] + arr[i]

# print(sums)
sums.insert(0, 0)
dp = []

for i in range(n):
    temp = []
    for j in range(n):
        temp.append(0)
    
    dp.append(temp)


for i in range(1, n):
    for j in range(0, n-i):
        start = j
        end = start + i

        min_ = float('inf')
        for k in range(start, end):
            min_ = min(min_, dp[start][k] + dp[k+1][end] + sums[end+1] - sums[start])
        
        dp[start][end] = min_

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

D = [-1] * (n**2)
for i in range(n):
    D[i*n + i] = 0

S = [A[0]]
for i in range(1, n):
    S.append(A[i] + S[-1])
S.append(0)

# print(D)
# print(S)

def merge(l, r):
    # print(l,r)
    if D[l*n + r] != -1:
        return D[l*n + r]
    else:
        ans = float("inf")
        for i in range(l, r):
            ans = min(ans, merge(l, i) + merge(i+1, r) + S[r] - S[l-1])
        D[l*n + r] = ans
        return ans

print(merge(0, n-1))
# print(D)

Submission status: Accepted

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


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

a_array = na()
sum_array = [0]
slime = 0
for a in a_array:
    slime += a
    sum_array.append(slime)

INF = 10 ** 15
ans = [[INF] * N for _ in range(N)]


def solve(l, r):
    # print(l,r)
    if ans[l][r] != INF:
        return ans[l][r]
    if l == r:
        ans[l][r] = 0
        # print(l,r,ans[l][r])
        return 0
    slime_sum = sum_array[r+1] - sum_array[l]
    # print(l,r,"slime",slime_sum)
    for i in range(l, r):
        ans[l][r] = min(ans[l][r], solve(l, i) + solve(i+1, r) + slime_sum)
    # print(l,r,ans[l][r])
    return ans[l][r]


print(solve(0, N-1))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

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

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

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

# 区間の長さが小さい順にループする(1～N)
for i in range(N): # 区間の長さ
  for l in range(N - i):
    r = l + i
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]
# dp[i][j]は区間[i, j)での最小のコスト

# メモ化再帰
def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    if dp[l][r] != -1:
        return dp[l][r]

    # r - l >= 2である
    # iを媒介にdpを貪欲に探索する。
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def cumsum(a):
    """l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    l = [None] * (len(a)+1)
    for i,num in enumerate(a):
        l[i] = c
        c += num
    l[-1] = c
    return l
s = cumsum(a)

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	def pre_sum(arr):
		ans = [arr[0]]
		for i in range(1,len(arr)):
			ans.append(ans[-1]+ arr[i])
		return ans
	for test in range(tests):
		n = inp()
		a = inlt()
		ans = 0
		dp = [[sys.maxsize for j in range(n)] for i in range(n)]
		pre = pre_sum(a)
		# print(pre)
		for i in range(n-1,-1,-1):
			dp[i][i] = 0
			for j in range(i+1,n,1):
				for k in range(i+1,j+1):
					dp[i][j] = min(dp[i][j] , dp[i][k-1] + dp[k][j] + pre[j] -pre[i] + a[i])
		# print(dp)
		print(dp[0][-1])



		
		


if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
import itertools

n=int(input())
a=list(map(int,input().split()))
s=[0]+list(itertools.accumulate(a))

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

print(dp[0][n])