Optimal Matrix Multiplication P11455


Statement
 

pdf   zip

thehtml

Given two matrices with dimensions n1 × n2 and n2 × n3, the cost of the usual multiplication algorithm is Θ(n1 n2 n3). For simplicity, let us consider that the cost is exactly n1 n2 n3.

Suppose that we must compute M1 × … × Mm, where every Mi is an ni × ni+1 matrix. Since the product of matrices is associative, we can choose the multiplication order. For example, to compute M1 × M2 × M3 × M4, we could either choose (M1 × M2) × (M3 × M4), with cost n1 n2 n3 + n3 n4 n5 + n1 n3 n5, or either choose M1 × ((M2 × M3) × M4), with cost n2 n3 n4 + n2 n4 n5 + n1 n2 n5, or three other possible orders.

Write a program to find the minimum cost of computing M1 × … × Mm.

Input

Input consists of several cases, each one with m followed by the m + 1 dimensions. Assume 2 ≤ m ≤ 100 and 1 ≤ ni ≤ 104.

Output

For every case, print the minimum cost to compute the product of the m matrices.

Public test cases

  • Input

    2   1 2 3
3   10 20 30 40
10  9000 4000 3500 8000 2000 7500 6000 1000 8500 5500 7000

    Output

    6
18000
302250000000
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++