ALDS1_10_B: Matrix Chain Multiplication

行列の積を求める時の掛け算の数を最小にするという問題

行列は微妙に苦手意識があるんだけれどもなぜかというとどっちが行で
どっちが列か不安になるから、というくらい
えーと行列の掛け算はと
m行n列の行列×n行l列の行列は掛け算できて積はm行l列
その時の掛け算の回数はm×n×l回かな

まずは素直に書いてみるところから
長い行列の積を二つの部分に分解して再帰すればよさそう

from sys import maxsize

def count_2(m1, m2):
    assert m1[1] == m2[0]
    return m1[0] * m1[1] * m2[1]

def result_2(m1, m2):
    return (m1[0], m2[1])

def count(m):
    assert len(m) > 0

    if len(m) == 1:
        return m[0], 0
    elif len(m) == 2:
        return result_2(m[0], m[1]), count_2(m[0], m[1])

    min_count = maxsize
    min_result = (0, 0)
    for i in range(1, len(m)):
        m1, c1 = count(m[:i])
        m2, c2 = count(m[i:])
        m3, c3 = result_2(m1, m2), count_2(m1, m2)
        c = c1 + c2 + c3
        if c < min_count:
            min_count = c
            min_result = m3

    return min_result, min_count

def main():
    n = int(input())

    m = []
    for _ in range(n):
        m.append(tuple(int(x) for x in input().split()))
    _, c = count(m)
    print(c)

if __name__ == '__main__':
    main()

予定通りTLE