Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Matrix-chain Multiplication

  The goal of the matrix-chain multiplication problem is to find the most efficient way to multiply given $n$ matrices $M_1, M_2, M_3,...,M_n$.

  Write a program which reads dimensions of $M_i$, and finds the minimum number of scalar multiplications to compute the maxrix-chain multiplication $M_1M_2...M_n$.

Input

  In the first line, an integer $n$ is given. In the following $n$ lines, the dimension of matrix $M_i$ ($i = 1...n$) is given by two integers $r$ and $c$ which respectively represents the number of rows and columns of $M_i$.

Output

  Print the minimum number of scalar multiplication in a line.

Constraints

$1 \leq n \leq 100$

$1 \leq r, c \leq 100$

Sample Input 1

6
30 35
35 15
15 5
5 10
10 20
20 25

Sample Output 1

15125



Sample input:
6
30 35
35 15
15 5
5 10
10 20
20 25


Sample output:
15125

Submission status: Wrong Answer

Solution code:
import sys

def get_min_cost(n, p):
	m = [[0 for x in range(n+1)] for x in range(n+1)]
	for s in range(n):
		i = 1
		for j in range(s+2, n):
			m[i][j] = sys.maxsize
			for k in range(i, j+1):
				m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
			i+=1	
	return m[1][n]

n = int(input())
p = [0] * (n+1)
j = 0
for i in range(n):
	a = list(map(int, input().split()))
	if i == 0:
		p[j] = a[0]
		j += 1
	p[j] = a[1]
	j += 1
print(get_min_cost(n, p))

Submission status: Wrong Answer

Solution code:
import sys, copy

num = int(sys.stdin.readline())

if num==1:
    print(0)
    quit()
    
mm = list(map(int, sys.stdin.readline().split()))
for _ in range(num-1):
    mm.append(int(sys.stdin.readline().split()[1]))

used = [False] * num
seq = [0] * (num-2)
minv = 0
j=mm[1]
for i in mm[2:]:
    minv += i*j
    j=i
minv *= mm[0]    

print('min=',minv)
def sequence(n, k, m, t):
    global minv, used, seq
    if k==m:
        t += mm[0]*mm[used[1:].index(False)+1]*mm[num]
        if minv>t:    minv = t
    else:
        for i in range(1,n+1):
            if used[i]: continue
            seq[m] = i
            used[i]=True

            l=i-1
            while l>0 and used[l]:     l-=1
            u=i+1
            while u<num and used[u]:   u+=1
            v = mm[l]*mm[i]*mm[u]
            if minv>t+v: sequence(n, k, m+1, t+v)
            used[i]=False

sequence(num-1, num-2, 0, 0)

print(minv)

Submission status: Wrong Answer

Solution code:
n = int(input())
rc = [list(map(int, input().split())) for _ in range(n)]
rc_min = rc.index(min(rc))

def calc(rc):
    total = 0
    for i, irc in enumerate(rc):
        if i ==0:
            r, c = irc
        else:
            total += r * c * irc[1]
            c = irc[1]
    return r, c, total
def reverse_calc(rc):
    total = 0
    for i, irc in enumerate(rc[::-1]):
        if i ==0:
            r, c = irc
        else:
            total += r * c * irc[0]
            r = irc[0]
    return r, c, total

former = rc[:rc_min]
latter = rc[rc_min:]
total=r1=c1=r2=c2 =0
if former:
    r1, c1, ret = reverse_calc(rc[:rc_min])
    total += ret
if latter:
    r2, c2, ret =calc(rc[rc_min:])
    total += ret
if former and latter:
    total += r1 * c1 * c2
print(total)

Submission status: Wrong Answer

Solution code:
N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
	cache[(i, i+1)] = 0
def dfs(left, rifht):
	if (left, rifht) in cache:
		return cache[(left, rifht)]
	min_cost = float("inf")
	for mid in xrange(left+1, rifht):
		tmp = M[left][0]*M[mid-1][1]*M[rifht-1][1]
		tmp += dfs(left, mid)
		tmp += dfs(mid, rifht)
		if min_cost > tmp:
			min_cost = tmp
		cache[(left, rifht)] = min_cost
		return min_cost 
print dfs(0, len(M))

Submission status: Wrong Answer

Solution code:
import sys

p=[0 for i in range (101)]
m=[[0 for i in range(100)]for i in range(100)]

def MatrixChain(n) : 
	for i in range(1,n+1) : m[i][i] = 0;
	for l in range(2,n+1) :
		for i in range(1,n-l+2) : 
			j = i + l - 1
			m[i][j] = float('Infinity')
			for k in range(i,j) :
				q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				m[i][j] = m[i][j] if m[i][j] <= q else q

n = int(input())
for i in range(n) :
	input_num = input()
	input_num = input_num.split(' ')
	p[i] = int(input_num[0][0])
	p[i+1] = int(input_num[1])

MatrixChain(n)
print(m[1][n])

Submission status: Wrong Answer

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n+1)] for j in range(n+1)]
  
  for l in range(2, n):
    for i in range(1, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j-1))
  
  return m[0][n-1]

n = input()
M = []

for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Wrong Answer

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n)] for j in range(n)]
  
  for l in range(2, n):
    for i in range(1, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j-1))
  
  return m[0][n-1]

n = input()
M = []

for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Wrong Answer

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n)] for j in range(n)]
  
  for l in range(2, n):
    for i in range(1, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j))
  
  return m[0][n-1]

n = input()
M = []

for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Wrong Answer

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n)] for j in range(n)]
  
  for l in range(2, n+1):
    for i in range(1, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j))
  
  return m[0][n-1]

n = input()
M = []

for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]
for i in range(1, n+1):
    p[i-1], p[i] = map(int, raw_input().split())
     
for l in range(2, n):
    for i in range(1, n-l+2):
        j = i+l-1
        m[i][j] = float("inf")
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
 
print m[1][n]

Submission status: Wrong Answer

Solution code:
def matrix(X):
    m = [[0 for i in range(len(X))] for j in range(len(X))]
    
    for l in range(2, len(X)+1):
        for i in range(0, len(X)-l+1):
            j = i + l - 1
            for k in range(i, j - 1):
                m[i][j] = min(m[i][k] + m[k+1][j] + X[i][0]*X[k][1]*X[j][1] for k in range(i, j))

    print m[0][len(X)-1]

n = input()
X = []

for i in range(n):
    X.append(map(int, raw_input().split()))

matrix(X)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
p = [0 for i in range(101)]
m = [[0 for i in range(101)] for j in range(101)]

for i in range (1,n+1):
    m[i][i] = 0
    p[i-1],p[i] = map(int,raw_input().split())
   
for k in range (2,n+1):
    for i in range(1,n - k + 2):
        j = i + k - 1
        m[i][k] = 10**10
        for l in range(i,k):
            m[i][j] = min(m[i][j], m[i][l] + m[l+1][j] + p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
p = [0 for i in range(101)]
m = [[0 for i in range(101)] for j in range(101)]

for i in range (1, n + 1):
    m[i][i] = 0
    p[i-1],p[i] = map(int,raw_input().split())
   
for k in range (2, n + 1):
    for i in range(1, n - k + 2):
        j = i + k - 1
        m[i][k] = 10**10
        
        for l in range(i, k):
            m[i][j] = min(m[i][j], m[i][l] + m[l+1][j] + p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
p = [0 for i in xrange(101)]
m = [[0 for i in xrange(101)] for j in xrange(101)]

for i in xrange (1, n + 1):
    m[i][i] = 0
    p[i-1],p[i] = map(int,raw_input().split())
   
for k in range (2, n + 1):
    for i in range(1, n - k + 2):
        j = i + k - 1
        m[i][k] = 10**10
        for l in xrange(i, k):
            m[i][j] = min(m[i][j], m[i][l] + m[l+1][j] + p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
p = [0 for i in range(101)]
m = [[0 for i in range(101)] for j in range(101)]

for i in range (1, n + 1):
    m[i][i] = 0
    p[i-1],p[i] = map(int,raw_input().split())
   
for k in range (2, n + 1):
    for i in range(1, n - k + 2):
        j = i + k - 1
        m[i][k] = 10**10
        for l in range(i, j):
            m[i][j] = min(m[i][j], m[i][l] + m[l+1][j] + p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Wrong Answer

Solution code:
def main():
    n = int(raw_input())
    m = [ [0] * n for _ in xrange(n)]
    p = [ 0 for _ in xrange(n+1)]
    for i in xrange(n):
        a = map(int, raw_input().split())
        if i == 0:
            p[0] = a[0]
            p[1] = a[1]
        else:
            p[i+1] = a[1]

    for l in xrange(2,n+1):
        for i in xrange(0,n-l+1):
            j = i + l -1
            m[i][j] = float('inf')
            for k in xrange(i,j):
                m[i][j] = min(m[i][j], m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j])
    
    print m, m[0][n-1]
    return 0

main()

Submission status: Wrong Answer

Solution code:
"""
n = input().split()

n = input()
nele = int(n[0])
list = range(1,nele+1)

nrow = {}
ncol = {}
for i in list:
	nrow[i] = int(n[i*2-1])
	ncol[i] = int(n[i*2])
"""

n = input()
nele = int(n[0])
list = range(1,nele+1)
nrow = {}
ncol = {}
for i in list:
	n = input().split()
	nrow[i] = int(n[0])
	ncol[i] = int(n[1])


#print(nrow, ncol)


min = -1
cur = -1
route = []
done = []

for i in list:
	route.append(0)

#print(route)

depth = -1
min = -1
def tansaku(prev):
	
	global depth
	depth += 1
	
	global nrow
	global ncol
	global min
	global route
	
	done = route[:]
	
	for i in list:
#		print(depth, i, route, done)
		
		if i in done:
			continue
		
		next = i
		done.append(next)
		
		if depth == 0:
			route[depth] = next
			tmp = 0
			min = tansaku(tmp)
			continue
		
		tmp = prev + nrow[route[depth-1]] * ncol[next]
#		print(tmp)
		
		if tmp > min and min != -1:
#			print("aaa")
			continue
		else:
			route[depth] = next
			if depth >= nele-1:
#				print("bbb")
				min = tmp
			else:
#				print("ccc")
				min = tansaku(tmp)
	
	depth -= 1
	route[depth] = 0
#	print("min:", min)
	return min

min = tansaku(0)

print(min)

Submission status: Wrong Answer

Solution code:
"""
n = input().split()

n = input()
nele = int(n[0])
list = range(1,nele+1)

nrow = {}
ncol = {}
for i in list:
	nrow[i] = int(n[i*2-1])
	ncol[i] = int(n[i*2])
"""

n = input()
nele = int(n[0])
list = range(1,nele+1)
nrow = {}
ncol = {}
for i in list:
	n = input().split()
	nrow[i] = int(n[0])
	ncol[i] = int(n[1])


#print(nrow, ncol)


min = -1
cur = -1
route = []
done = []

for i in list:
	route.append(0)

#print(route)

depth = -1
min = -1
def tansaku(prev, row_prev):
	
	global depth
	depth += 1
	
	global nrow
	global ncol
	global min
	global route
	
	done = route[:]
	
	for i in list:
#		print(depth, i, route, done)
		
		if i in done:
			continue
		
		next = i
		done.append(next)
		
		if depth == 0:
			route[depth] = next
			tmp = 0
			row_next = nrow[next]
			min = tansaku(tmp, row_next)
			continue
#		print(route, route[depth-1], next, nrow[route[depth-1]], ncol[next], prev)
#		tmp = prev + nrow[route[depth-1]] * ncol[next]
		print(prev, row_prev, ncol[next])
#		tmp = prev + row_prev * ncol[next]
		row_next = ncol[next]
#		print(depth, tmp)
		
		if tmp > min and min != -1:
#			print("aaa")
			continue
		else:
			route[depth] = next
			if depth >= nele-1:
#				print("bbb")
				min = tmp
			else:
#				print("ccc")
				min = tansaku(tmp, row_next)
	
	depth -= 1
	route[depth] = 0
	print("min:", min)
	return min

min = tansaku(0, 0)

print(min)

Submission status: Wrong Answer

Solution code:
"""
n = input().split()

n = input()
nele = int(n[0])
list = range(1,nele+1)

nrow = {}
ncol = {}
for i in list:
	nrow[i] = int(n[i*2-1])
	ncol[i] = int(n[i*2])
"""

n = input()
nele = int(n[0])
list = range(1,nele+1)
nrow = {}
ncol = {}
for i in list:
	n = input().split()
	nrow[i] = int(n[0])
	ncol[i] = int(n[1])


#print(nrow, ncol)


min = -1
cur = -1
route = []
done = []

for i in list:
	route.append(0)

#print(route)

depth = -1
min = -1
def tansaku(prev, row_prev):
	
	global depth
	depth += 1
	
	global nrow
	global ncol
	global min
	global route
	
	done = route[:]
	
	for i in list:
#		print(depth, i, route, done)
		
		if i in done:
			continue
		
		next = i
		done.append(next)
		
		if depth == 0:
			route[depth] = next
			tmp = 0
			row_next = nrow[next]
			min = tansaku(tmp, row_next)
			continue
#		print(route, route[depth-1], next, nrow[route[depth-1]], ncol[next], prev)
#		tmp = prev + nrow[route[depth-1]] * ncol[next]
#		print(prev, row_prev, ncol[next])
		tmp = prev + row_prev * ncol[next]
		row_next = ncol[next]
#		print(depth, tmp)
		
		if tmp > min and min != -1:
#			print("aaa")
			continue
		else:
			route[depth] = next
			if depth >= nele-1:
#				print("bbb")
				min = tmp
			else:
#				print("ccc")
				min = tansaku(tmp, row_next)
	
	depth -= 1
	route[depth] = 0
#	print("min:", min)
	return min

min = tansaku(0, 0)

print(min)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(range(n+2))

for i in range(1,n+1):
    p[i], p[n+1] = map(int, input().split())

# table[i][j] : M_i??????M_j??????????????????????°?????????°
table = [[0] * (n+1) for i in range(n+1)]

# ??£????????£???2????????????????????????
for i in range(1,n):  # 1<=i,i+1<=n
    table[i][i+1] = p[i]*p[i+1]*p[i+2]


for k in range(3, n+1):    # ?????????k???????????????????????????3<=k<=n
    for i in range(1,n+2-k): # M_i?????????1<=i<=n-k+1
        j = i + k - 1      # M_j?????§???k??????

        table[i][j] = float('inf')

        for x in range(i, j): # M_i~M_x??¨M_(x+1)~M_j??§????????????(i<=x,x+1<=j<=n)
            print(i, x, j)
            cost = table[i][x] + table[x+1][j] + p[i]*p[x+1]*p[j+1]
            table[i][j] = min(table[i][j], cost)
            

print(table[1][n])

Submission status: Wrong Answer

Solution code:
n = int(input())
INF = 10**9
P = [list(map(int, input().split())) for i in range(n)]
m = [[0]*n for i in range(n)]

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + P[i - 1][0] * P[k][1] * P[j][1])

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num_mat = int(stdin.readline())
    data = [int(s) for s in stdin.readline().split()]
    for _ in range(num_mat-1):
        _, row = (int(s) for s in stdin.readline().split())
        data.append(row)
    num_dat = len(data)

    bin_op = tuple(data[i]*data[i+1]*data[i+2] for i in range(num_dat-2))
    parts = [(data[0]*data[1], data[-2]*data[-1]), bin_op]

    for j in range(3, num_mat):
        part = parts[-1]
        new_part = []
        for i in range(num_dat-j):
            a = data[i]
            b = data[i+1]
            c = data[i+j-1]
            d = data[i+j]
            new_part.append(min(part[i] + a*c*d, part[i+1] + a*b*d))
        parts.append(new_part)

    L = data
    if num_mat > 1:
        print(min(parts[i][0] + parts[-(i+1)][-1] +
                  L[0]*L[i+1]*L[-1] for i in range(len(parts))))
    else:
        print(0)


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num_mat = int(stdin.readline())
    data = [int(s) for s in stdin.readline().split()]
    for _ in range(num_mat-1):
        _, row = (int(s) for s in stdin.readline().split())
        data.append(row)
    num_dat = len(data)

    bin_op = tuple(data[i]*data[i+1]*data[i+2] for i in range(num_dat-2))
    parts = [(data[0]*data[1], data[-2]*data[-1]), bin_op]

    for j in range(3, num_mat):
        part = parts[-1]
        new_part = []
        for i in range(num_dat-j):
            a = data[i]
            b = data[i+1]
            c = data[i+j-1]
            d = data[i+j]
            new_part.append(min(part[i] + a*c*d, part[i+1] + a*b*d))
        parts.append(new_part)

    L = data
    if num_mat < 2:
        print(0)
    elif num_mat < 3:
        print(data[0]*data[1]*data[2])
    else:
        print(min(parts[i][0] + parts[-(i+1)][-1] +
                  L[0]*L[i+1]*L[-1] for i in range(len(parts))))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

n = int(sys.stdin.readline())
MM = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

amin=1000000000000
for t in itertools.permutations(range(n-1)):
    mm=[m[:] for m in MM]
    o = list(t)
    ans=0
    for _ in range(n-1):
        i = o.pop(0)
        ans += mm[i][0]*mm[i+1][1]*mm[i][1]

        mm[i][1] = mm[i+1][1]
        mm.pop(i+1)
        
        for j in range(len(o)):
            if o[j]>i: o[j] -=1

    if amin>ans: amin=ans


print(amin)

Submission status: Time Limit Exceeded

Solution code:
import sys, itertools

n = int(sys.stdin.readline())
if n==1:
    print(0)
    quit()

MM = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

amin = 0
m = MM[0][:]
for i in range(n-1):
    amin += m[0]*m[1]*MM[i+1][1]
    m[1]=MM[i+1][1]


for t in itertools.permutations(range(n-1), n-2):

    mm=[m[:] for m in MM]
    o = list(t)
    ans=0
    for _ in range(n-2):
        i = o.pop(0)
        ans += mm[i][0]*mm[i+1][1]*mm[i][1]
        if ans>amin: break
        mm[i][1] = mm[i+1][1]
        mm.pop(i+1)
        
        for j in range(len(o)):
            if o[j]>i: o[j] -=1
    else:
        ans += mm[0][0]*mm[0][1]*mm[1][1]
        if amin>ans: amin=ans


print(amin)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy

num = int(sys.stdin.readline())

if num==1:
    print(0)
    quit()
    
mm = list(map(int, sys.stdin.readline().split()))
for _ in range(num-1):
    mm.append(int(sys.stdin.readline().split()[1]))

used = [False] * num
seq = [0] * (num-2)
minv = 0
j=mm[1]
for i in mm[2:]:
    minv += i*j
    j=i
minv *= mm[0]    

def sequence(n, k, m, t):
    global minv, used, seq
    if k==m:
        t += mm[0]*mm[used[1:].index(False)+1]*mm[num]
        if minv>t:    minv = t
    else:
        for i in range(1,n+1):
            if used[i]: continue
            seq[m] = i
            used[i]=True

            l=i-1
            while l>0 and used[l]:     l-=1
            u=i+1
            while u<num and used[u]:   u+=1
            v = mm[l]*mm[i]*mm[u]
            if minv>t+v: sequence(n, k, m+1, t+v)
            used[i]=False

sequence(num-1, num-2, 0, 0)

print(minv)

Submission status: Time Limit Exceeded

Solution code:
N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):#[left, right)
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    return min_cost
print dfs(0, len(M))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))

dp = [0 for _ in range(n)]
for i in range(n-1):
    dp[i] = data[i][0] * data[i][1] * data[i+1][1]



def mul(i, j):
    if i == j:
        return 0
    elif i == j - 1:
        return dp[i]
    num = 100000
    for k in range(i, j):
        num = min(num, mul(i, k) + mul(k+1, j) + data[i][0] * data[k][1] * data[j][1])
    return num

print(mul(0, n-1))

Submission status: Accepted

Solution code:
n = int(input())
p = [item for sublist in [[int(input().split()[1])] if i != 0 else list(map(int, input().split())) for i in range(n)] for item in sublist]

def memolize(f):
    cache = {}

    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memolize
def calcMatrixOrder(i, j):
    if i == j :
        return 0
    return min([calcMatrixOrder(i, k) + calcMatrixOrder(k + 1, j) + p[i]*p[k+1]*p[j + 1] for k in range(i, j)])

print(calcMatrixOrder(0, n - 1))

Submission status: Accepted

Solution code:
import sys

def get_min_cost(n, p):
	m = [[0 for x in range(n+1)] for x in range(n+1)]
	for s in range(n):
		i = 1
		for j in range(s+2, n+1):
			m[i][j] = sys.maxsize
			for k in range(i, j):
				m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
			i+=1	
	return m[1][n]

n = int(input())
p = [0] * (n+1)
j = 0
for i in range(n):
	a = list(map(int, input().split()))
	if i == 0:
		p[j] = a[0]
		j += 1
	p[j] = a[1]
	j += 1
print(get_min_cost(n, p))

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())

m = list(map(int, sys.stdin.readline().split()))
for _ in range(n-1):
    _, a = sys.stdin.readline().split()
    m.append(int(a))

c = [[-1 for _ in range(n)] for _ in range(n)]

def val(a, b):
    if a==b: return 0
    if c[a][b]>0: return c[a][b]
    c[a][b]=val(a+1,b)+m[a-1]*m[a]*m[b]
    for k in range(a+1, b):
        v=val(a,k)+val(k+1,b)+m[a-1]*m[k]*m[b]
        if c[a][b]>v: c[a][b]=v
    return c[a][b]

print(val(0, n-1))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
P=[0]*(N+1)
for i in range(N):
    r,c=MAP()
    if i==0:
        P[i]=r
    P[i+1]=c

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())



def solve():
    n = int(input())
    mat_list = []
    for i in range(n):
        mat_list.append(list(map(int, input().split())))
    dprint(mat_list)

    # 掛け始めのidxと掛け終わりのidxをi, jとし、計算回数を持つメモ
    memo = [[0 for i in range(n)] for i in range(n)]

    def calc(start, end):
        dprint("*", start, end)
        # 1つの行列なら0
        if end == start:
            return 0

        # メモがあれば返す
        if memo[start][end] != 0:
            return memo[start][end]

        # 2つの行列なら、答えを計算しメモ追記
        if end - start == 1:
            cost = mat_list[start][0] * mat_list[start][1] * mat_list[end][1]
            memo[start][end] = cost
            dprint(start, end, cost)
            return cost

        # 3つ以上なら、再帰
        min_cost = -1
        if end - start >= 2:
            for right_start in range(start+1, end+1):
                left = calc(start, right_start-1)
                right = calc(right_start, end)
                cost = left + right + mat_list[start][0] * mat_list[right_start][0] * mat_list[end][1]
                if min_cost == -1 or min_cost > cost:
                    min_cost = cost
                dprint(start, end, right_start, min_cost, cost)

        memo[start][end] = min_cost
        return min_cost

    ans = calc(0, n-1)
    dprint(memo)
    print(int(ans))

solve()

Submission status: Accepted

Solution code:
N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    cache[(left, right)] = min_cost
    return min_cost
print dfs(0, len(M))

Submission status: Accepted

Solution code:
def memoize(f):  
    cache = {}  
    def helper(x):  
        if x not in cache:              
            cache[x] = f(x)  
        return cache[x]  
    return helper 

def split_rc(rc):
    for i in range(1, len(rc)):
        yield rc[:i], rc[i:]

@memoize
def cost(rc):
    if len(rc) == 1:
        return 0
    return min(calc_cost(first, second) for first, second in split_rc(rc))

def calc_cost(first, second):
    return cost(first) + cost(second) + first[0][0] * first[-1][1] * second[-1][1]

n = int(input())
rc = tuple(tuple(map(int, input().split())) for _ in range(n))
print(cost(rc))

Submission status: Accepted

Solution code:
import sys

p=[0 for i in range (101)]
m=[[0 for i in range(100)]for i in range(100)]

def MatrixChain(n) : 
	for i in range(1,n+1) : m[i][i] = 0;
	for l in range(2,n+1) :
		for i in range(1,n-l+2) : 
			j = i + l - 1
			m[i][j] = float('Infinity')
			for k in range(i,j) :
				q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				m[i][j] = m[i][j] if m[i][j] <= q else q

n = int(input())
for i in range(n) :
	p[i], p[i+1] = map(int, input().split())

MatrixChain(n)
print(m[1][n])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
n = int(input())
M = [tuple(list(map(int, input().split()))) for i in range(n)]

# best[i][i + j] : M_i * M_i+1 * ... * M_i+j?????????cost??¨??????
best = [[float('inf') for j in range(n)] for i in range(n)]
for j in range(0, n):
    for i in range(n - j):
        l = []
        for k in range(j):
            c1 = best[i][i + k]
            c2 = best[i + k + 1][i + j]
            c3 = M[i][0] * M[i + k][1]  * M[i + j][1]
            l.append(c1 + c2 + c3)
        best[i][i + j] = 0 if len(l) == 0 else min(l)
print(best[0][n-1])

Submission status: Accepted

Solution code:
n = int(raw_input())

def update(i,l,n,ms,dp):
    min_val = 10000000000000
    for k in range(1,l):
        val = dp[i][k]+dp[i+k][l-k]+ms[i][0]*ms[i+k-1][1]*ms[i+l-1][1]
        if min_val > val:
            min_val = val
    return min_val

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

ms = []
for i in range(n):
    r,c = map(int, raw_input().split(' '))
    ms.append((r,c))

for l in range(2,n+1):
    for i in range(n):
        if i + l > n: break
        dp[i][l] = update(i,l,n,ms,dp)

print dp[0][n]

Submission status: Accepted

Solution code:
def solve(a):
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
print solve(M)

Submission status: Accepted

Solution code:
def solve(a):
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
print solve(M)

Submission status: Accepted

Solution code:
def solve(a):
 n = len(a)
 cost = [[0 for i in range(n)] for j in range(n)]
 for length in range(2, n+1):
  for i in range(0, n-length+1):
   k = i+length-1
   def f(i,j,k):
    return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return cost[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print solve(M)

Submission status: Accepted

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n)] for j in range(n)]
  
  for l in range(2, n+1):
    for i in range(0, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j))
  
  return m[0][n-1]

n = input()
M = []

for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Accepted

Solution code:
def edit_distance(M):
  n = len(M)



  m = [[0 for i in range(n)] for j in range(n)]
   
  for long in range(2, n+1):

    for i in range(0, n-long+1):

      j = i + long - 1

      def a(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(a(i, k, j) for k in range(i, j))
   
  return m[0][n-1]
 
n = input()
M = []
 
for i in range(n):
  M.append(map(int, raw_input().split()))
print edit_distance(M)

Submission status: Accepted

Solution code:
def cost(i,k,j):
 return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]

n = input()
p = []
m = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
 p.append(map(int, raw_input().split()))

N = len(p)
for l in xrange(2,N+1):
 for i in xrange(0,N-l+1):
   j = i+l-1
   m[i][j] = min(cost(i,k,j) for k in xrange(i,j))

print m[0][N-1]

Submission status: Accepted

Solution code:
n = int(input())
p = []
a,b = [int(x) for x in input().split()]
p.append(a)
p.append(b)
for i in range(1, n):
    c,d = [int(x) for x in input().split()]
    p.append(d)
# end input
# create dp table
dp = []
for x in range(n+1):
    dp.append([0] * (n+1))

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

        for k in range(i, j):
            tmp = dp[i][k] + dp[k+1][j] + (p[i-1] * p[k] * p[j])
            if dp[i][j] > tmp:
                dp[i][j] = tmp
#print(dp)
print(dp[1][n])

Submission status: Accepted

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + M[i][0] * M[k][1] * M[j][1]
 
n = input()
M = []
m = [[ 0 for i in range(n) ] for j in range(n) ]
for i in range(n):
  M.append( map (int, raw_input().split() ) )
 
M_long = len(M)
for l in range( 2,M_long+1 ):
  for i in range( 0,M_long-l+1 ):
    j = i+l-1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][M_long-1]

Submission status: Accepted

Solution code:
n = input()
M = []
 
def scalar(n):
   m = [[0 for i in range(len(n))] for j in range(len(n))]
 
   for l in range(2, len(n)+1):
      for i in range(0, len(n)-l+1):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))
 
   print m[0][len(n)-1]
 
for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

Submission status: Accepted

Solution code:
MAX = pow(10, 8)
N = 100
p = [None] * (N + 1)
m = [None] * (N + 1)
n = input()
for i in xrange(1, n + 1):
    m[i] = [None] * (N + 1)
    m[i][i] = 0
    p[i - 1], p[i] = map(int, raw_input().split())
    
for l in xrange(2, n + 1):
    for i in xrange(1, n - l + 2):
        j = i + l - 1
        m[i][j] = MAX
        for k in xrange(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j])
print m[1][n]