Smart Matrix Multiplication

In a dreadful Algebra class, Deeparaj was asked to multiply out 32 matrices in general form.

Deeparaj knew that to multiply two matrices of order \(l \times m \) and \(m \times n \), he had to make \(lmn\) multiplications. Since the result is independent of the order in which the matrices are multiplied (as long as they are in the same sequence), Deeparaj figured out the way to minimize the number of multiplications that were needed.

Can you find the number of multiplications he performed?

Data


Input Format

  • The input consists of \(n+1\) lines, where \(n\) is the number of matrices.
  • The following input
1
2
3
4
5
d1
d2
.
.
d(n+1)

corresponds to \(n\) matrices of dimensions \(d_1 \times d_2, d_2 \times d_3, \ldots, d_n \times d_{n+1} \).

Example

  • Input:
1
2
3
4
10
30
5
60

  • Output: 4500

  • Explanation: The matrices are \(m_1, m_2, m_3\) of dimensions \(10 \times 30, 30 \times 5, 5 \times 60\). Multiplying them in the order \((m_1 \times m_2) \times m_3\) is the best you can do, and it takes \( 10 \times 30 \times 5 + 10 \times 5 \times 60 = 4500\) multiplications.

×

Problem Loading...

Note Loading...

Set Loading...