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:
n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [10, 20, 30, 40]
inf = 10**20
DP = [[None for r in range(n+1)] for l in range(n)]
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])


def f(l, r):
    if r <= l+1:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    DP[l][r] = S[r]-S[l]+min([f(l, i)+f(i, r) for i in range(l+1, r)])
    return DP[l][r]


print(f(0, n))

Submission status: Time Limit Exceeded

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

    dp = [[1<<60]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    for l in range(2, N+1):
        # right = left + len - 1でrightが[0, N - 1]のように
        for left in range(N-l+1):
            right = left + l-1
            #if right>= N: continue
            cost = cum_A[right+1] - cum_A[left]
            for k in range(left, right):
                tmp = dp[left][k] + dp[k+1][right] + cost
                dp[left][right] = min(dp[left][right], tmp)

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


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

arr = [int(x) for x in input().split()]

# dp[i][j] -> minscore to combine slices from i to j
# dp[0][n-1] : Res
# dp[i][i] -> 0
INF = 9745632585

dp = []

for i in range(n):
    temp = []
    for j in range(n):
        temp.append([INF,-1])
    dp.append(temp)

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i == j:
            dp[i][j][0] = 0
            dp[i][j][1] = arr[i]
            continue
        for k in range(i,j):
            temp = sum(dp[i][k])  + sum(dp[k+1][j])
            if dp[i][j][0] > temp:
                dp[i][j] =  [temp,dp[i][k][1] + dp[k+1][j][1]]

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

arr = [int(x) for x in input().split()]

# dp[i][j] -> minscore to combine slices from i to j
# dp[0][n-1] : Res
# dp[i][i] -> 0
INF = 974563258586

dp = []

for i in range(n):
    temp = []
    for j in range(n):
        temp.append([INF,-1])
    dp.append(temp)

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i == j:
            dp[i][j][0] = 0
            dp[i][j][1] = arr[i]
            continue
        for k in range(i,j):
            if k + 1 <= j:
                temp = sum(dp[i][k])  + sum(dp[k+1][j])
                if dp[i][j][0] > temp:
                    dp[i][j] =  [temp,dp[i][k][1] + dp[k+1][j][1]]

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

Submission status: Time Limit Exceeded

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

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

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

def main():
    ans = solve()

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

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


def solve():



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

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

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

    #fprint(size)

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


    for d in range(N):
        for l in range(N):
            for r in range(l+1, N):
                if l==r:
                    dp[l][r] = 0
                else:
                    dp[l][r] = min(dp[l][r],
                                   dp[l+1][r] + size[l][l] + size[l+1][r],
                                   dp[l][r-1] + size[r][r] + size[l][r-1])

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

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




#####################################################ライブラリ集ここから



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

def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

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

def iipt(l, listed=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

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


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


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


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

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


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


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


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

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

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


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

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


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

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

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


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

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

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
acc = [0] + list(accumulate(A))

# dp[i][j] := 区間[i, j]のスライムたちを１匹にまとめるのに必要なコスト
dp = [[None] * N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(i, j):
    if j - i == 1:
        dp[i][j] = A[i] + A[j]
        return dp[i][j]

    if dp[i][j] is not None:
        return dp[i][j]

    ret = float('inf')
    for x in range(i, j):
        ret = min(ret, dfs(i, x) + dfs(x + 1, j) + acc[j + 1] - acc[i])

    dp[i][j] = ret
    return ret


print(dfs(0, N - 1))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a= list(map(int, input().split()))
a+=a
INF=10**12
dp=[[[INF,0] for i in range(2*n+1)] for i in range(2*n+1)]
# dp[i][j][0]: コスト
# dp[i][j][1]:合成したスライムの合計

for i in range(n):
    for l in range(2*n-i):
        r=l+i
        if r==l:
            dp[l][r][1]=a[l]
            dp[l][r][0]=0
        else:
            # 合成の仕方を確定
            for k in range(l,r):
                dp[l][r][0]=min(dp[l][k][1]+dp[k+1][r][1]+dp[l][k][0]+dp[k+1][r][0],dp[l][r][0])
            dp[l][r][1]=dp[l][r-1][1]+a[r]
print(dp[0][n-1][0])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


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


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

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


print(dfs(1, n))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


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


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

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


print(dfs(1, n))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

Solution code:
N=int(input())
A=list(map(int,input().split()))
import numpy
B=[0]+list(numpy.cumsum(A))
dp=[[0]*(N+1) for i in range(N)]
#k:いくつのスライムを合体しているか
for k in range(2,N+1):
  #i:どこのスライムを起点に合体しているか
  for i in range(N-k+1):
    dp[i][k]=min(dp[i][j]+dp[i+j][k-j] for j in range(1,k))+B[i+k]-B[i]
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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

dp = [[INF] * (N + 10) for _ in range(N + 10)]
dp2 = [[0] * (N + 10) for _ in range(N + 10)]

for l in range(N):
    dp[l][l] = a[l]

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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

dp = [[INF] * (N + 10) for _ in range(N + 10)]
dp2 = [[0] * (N + 10) for _ in range(N + 10)]

for l in range(N):
    dp[l][l] = a[l]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    b = [0] + list(accumulate(a))
    dp = [[inf]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    for j in range(1, N):
        for l in range(0, N-j):
            r = l + j
            temp = b[r+1] - b[l]
            #区間の境界
            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+temp)
            
    print(dp[0][-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def calc(A,n,dp):
    if n==2:
        return A[0]+A[1]
    s=10**18
    for i in range(0,n-1):
        B=[]
        B=A[0:i]
        B.append(A[i]+A[i+1])
        B=B+A[i+2:]
        l=str(B)
        if l in dp:
            s=min(s,A[i]+A[i+1]+dp[l])
        else:
            d=calc(B,n-1,dp)
            s=min(s,A[i]+A[i+1]+d)
            dp[l]=d

    return s
n=int(input())
A=list(int(i) for i in input().split())
dp={}
print(calc(A,n,dp))
#for i in range(n):

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r):
  if r - l == 1:
    return (A[l], 0)
  ret = (INF, INF)
  for i in range(l+1, r):
    (lr, lc) = f(l, i)
    (rr, rc) = f(i, r)
    if lr+rr+lc+rc < ret[1]:
      ret = (lr+rr, lr+rr+lc+rc)
  return ret

print(f(0, N)[1])

Submission status: Time Limit Exceeded

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

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

INF = 10**18
dp = [[INF]*(n+1) for i in range(n+1)]
# dp[i][j]: 区間[i, j)のスライムを取り除いたコストの最小値
for i in range(n):
    dp[i][i+1] = 0
# 区間の幅(d)が狭い方から更新していく(d: 2, 3, ...n+1)
# d = 0, 1については初期化で更新した
for d in range(2, n+1):
    for i in range(n+1-d):
        j = i + d
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+B[j]-B[i])
#print(dp)
print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_n
N - Slimes / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 匹のスライムが横一列に並んでいます。 
最初、左から i 番目のスライムの大きさは ai です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 
スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 
合体前の 2 匹のスライムの大きさを x および y とすると、
    合体後のスライムの大きさは x+y となる。 
このとき、太郎君は x+y のコストを支払う。 
なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。
"""
#solve
def solve():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(n)]
    acc = [0] + list(itertools.accumulate(a))
    c = defaultdict(int)
    def f(l, r):
        tmp = inf
        if c[(l, r)]: return dp[l][r]
        c[(l,r)] = 1
        # print(dp, l, r)
        if l + 1 == r: return 0
        
        
        for i in range(l + 1, r):
            tmp = min(tmp, f(l, i) + f(i, r) + acc[r] - acc[l])
        # print(l,r)
        dp[l][r] = tmp
        return tmp
    print(f(0, n))
    # print(dp)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * (N + 1) for _ in range(N+ 1)]

accum = [0] * (N + 1)
for i in range(N):
    accum[i + 1] = accum[i] + A[i]

for m in range(1, N+1):
    for l in range(N):
        if m == 1:
            dp[l][l + m] = 0
        else:
            if l + m < N + 1:
                r = l + m
                dp[l][r] = min([dp[l][l+k] + dp[l+k][r] for k in range(1, m)]) + accum[r] - accum[l]

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def main(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    ret = 10**15
    for i in range(l, r):
        ret = min(ret, main(l, i)+main(i+1, r))
    ret += sum(A[l:r+1])
    dp[l][r] = ret
    return ret


print(main(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
#N

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

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


#dp[i][j]は[i,j)の範囲で全てをマージする最小コスト
inf=10**15
dp=[[inf]*(N+1) for _ in range(N+1)]

#区間[i,j)を[i,k)+[k,j)に分けて考える
for d in range(1,N+1):#dはj-i
    for i in range(N+1):
        j=i+d
        if j>N:
            break
        if d==1:
            dp[i][j]=0
        else:
            for k in range(i,j):
                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k][j]+S[j]-S[i])
            
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
#N
import copy
from collections import defaultdict
dd = defaultdict(int)

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

def rep(L):
    if len(L)==1:
        return 0
    S='-'.join(map(str, L))
    if dd[S]!=0:
        return dd[S]
    temp=10**15
    for i in range(len(L)-1):
        LL=copy.deepcopy(L)
        LL[i]+=LL[i+1]
        LL.pop(i+1)
        temp=min(temp,rep(LL)+L[i]+L[i+1])
    dd[S]=temp
    return temp
        
rep(a)
S='-'.join(map(str, a))
print(dd[S])

Submission status: Time Limit Exceeded

Solution code:
#N
import copy
from collections import defaultdict
dd = defaultdict(int)

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

def rep(L):
    if len(L)==1:
        return 0
    S='-'.join(map(str, L))
    if dd[S]!=0:
        return dd[S]
    temp=10**15
    for i in range(len(L)-1):
        LL=copy.deepcopy(L)
        LL[i]+=LL[i+1]
        LL.pop(i+1)
        temp=min(temp,rep(LL)+L[i]+L[i+1])
    dd[S]=temp
    return temp
        
rep(a)
S='-'.join(map(str, a))
print(dd[S])

Submission status: Time Limit Exceeded

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

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

memo = [[float('inf')]*410 for _ in range(410)]
visit = [[False]*410 for _ in range(410)]

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

def dp(l, r):
  if l == r:
    return 0
  if visit[l][r]:
    return memo[l][r]
  visit[l][r] = True
  res = float('inf')
  for c in range(l, r):
    res = min(res, dp(l, c)+dp(c+1, r)+B[r+1]-B[l])
  memo[l][r] = res
  return res

print(dp(0, n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0]+list(map(int, input().split()))

# 区間[i, j)の質量の合計はAcum[j-1] - Acum[i]
Acum = A[::]
for i in range(N):
    Acum[i + 1] += Acum[i]


cost = [[-1] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    cost[i][i + 1] = 0


def slime(i, j):
    if cost[i][j] != -1:
        return cost[i][j]

    res = 10 ** 18
    mass = Acum[j] - Acum[i]
    for x in range(i + 1, j):
        res = min(res, mass + slime(i, x) + slime(x, j))
    cost[i][j] = res
    return res


ans = slime(0, N)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 30 18:44:32 2020

@author: matsui
"""

def part(S,i,j):
    return S[i]-S[j-1]

import numpy as np


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

s=np.zeros(N+1)
s[0]=0
for i in range(1,N+1):
    s[i]=s[i-1]+a[i-1]

dp=np.zeros([N+1,N+1])

#for i in range(1,N+1):
#    dp[i][i]=a[i-1]
    
for i in range(1,N):
    dp[i][i+1]=a[i-1]+a[i]
    
  
for j in range(2,N):
    for i in range(1,N+1-j):
        dp[i][i+j]=part(s,i+j,i)
        c=[]
        for k in range(1,j+1):
            c.append(dp[i][i+j-k]+dp[i+j+1-k][i+j])
        dp[i][i+j]+=min(c)
        
        

#print(dp)      
print(int(dp[1][N]))

Submission status: Time Limit Exceeded

Solution code:

def asum(l,r):
	global cumsum
	l+=1
	r+=1
	return cumsum[r-1]-cumsum[l-1]
def check(l,r):
	global dp
	if l==r:
		return 0
	if l == r-1:
		return arr[l]+arr[r]
	if dp[l][r] != None:
		return dp[l][r]
	else:
		ans = 10**18
		for i in range(l, r):
			st1 = asum(l,i)
			st2 = asum(i,r+1)
			ans = min(st1 + st2 + check(l,i)+ check(i+1, r), ans)
		
		dp[l][r] = ans
		return ans





ll = int(input())
arr = [int(i) for i in input().split()]
cumsum = [0]

for i in arr:
	cumsum.append(cumsum[-1]+i)
dp = [[None for i in range(ll+1)] for j in range(ll+1)]
print(check(0, ll-1))

Submission status: Time Limit Exceeded

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

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

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

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


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

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


print(solve(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
def solve(N, slimes):
  # dp[L][R]: minimum cost to combine [L..R] into a single vertex
  dp = [[0 for _ in range(N)] for _ in range(N)]

  prefix_sum = [0 for _ in range(N + 1)]
  for i in range(N):
    prefix_sum[i + 1] = prefix_sum[i] + slimes[i]

  for L in range(N - 1, -1, -1):
    for R in range(L, N):
      if L == R:
        dp[L][R] = 0
      else:
        min_cost = float('inf')
        merge_cost = prefix_sum[R + 1] - prefix_sum[L]
        for i in range(L, R):   # i: [L..R-1]
          # min_cost = min(min_cost, dp[L][i] + dp[i + 1][R] + merge_cost)
          temp = dp[L][i] + dp[i + 1][R] + merge_cost
          if min_cost > temp:
            min_cost = temp
        dp[L][R] = min_cost

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

  
def iln(): return list(map(int, input().split()))
def iin(): return int(input())


N = iin()
slimes = iln()
solve(N, slimes)

Submission status: Time Limit Exceeded

Solution code:
def solve(N, slimes):
  # dp[L][R]: minimum cost to combine [L..R] into a single vertex
  dp = [[0 for _ in range(N)] for _ in range(N)]

  prefix_sum = [0 for _ in range(N + 1)]
  for i in range(N):
    prefix_sum[i + 1] = prefix_sum[i] + slimes[i]

  for L in range(N - 1, -1, -1):
    for R in range(L, N):
      if L == R:
        dp[L][R] = 0
      else:
        min_cost = float('inf')
        merge_cost = prefix_sum[R + 1] - prefix_sum[L]
        for i in range(L, R):   # i: [L..R-1]
          min_cost = min(
            min_cost,
            dp[L][i] + dp[i + 1][R] + merge_cost,
          )
        dp[L][R] = min_cost

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

  
def iln(): return list(map(int, input().split()))
def iin(): return int(input())


N = iin()
slimes = iln()
solve(N, slimes)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_n
import sys
sys.setrecursionlimit(20000000)

n = int(input())
a = list(map(int, input().split()))
b = [0]
sum_ = 0
for i in range(n):
    sum_ += a[i]
    b.append(sum_)

INIT = -1
dp = [[INIT for _ in range(n+1)] for _ in range(n+1)]

def solve(l, r):
    if dp[l][r] != -1:
        return dp[l][r]

    if abs(l - r) == 0:
        return 0

    res = 10**12
    for mid in range(l, r):
        res = min(res, solve(l, mid) + solve(mid+1, r))

    dp[l][r] = res + (b[r] - b[l-1])
    return dp[l][r]

print(solve(1, n))

Submission status: Time Limit Exceeded

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

cum = [[0]*(N) for i in range(N)]
for i in range(N):
  c = 0
  for j in range(i, N):
    c += A[j]
    cum[i][j] = c

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

for n in range(1, N+1):
  for i in range(N-n):
    j = i + n
    min_cost = 0
    for k in range(i, j):
      if min_cost == 0:
        min_cost = dp[i][k] + dp[k+1][j]
      else:
        min_cost = min(min_cost, dp[i][k]+dp[k+1][j])
    
    dp[i][j] = min_cost + cum[i][j]

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