PROGRAMMING:Matrix chain multiplication problem
The definition of matrix multiplication is as follows: let $$a $$be the matrix of $$m / times p $, and $$B $$be the matrix of $$P / times n $, then the product of $$a $$and $$B $$is the matrix of $$m / times n $, denoted as $$C = AB $, where the element of column $$J $$in row $$I $$of matrix $$C $$_{ Ij} $$can be expressed as: $$C_{ ij}=\Sigma _{ k=1}^p a_{ ik} \times b_{ kj} = a_{ i1}b_{ 1j}+a_{ i2}b_{ 2j}+\cdots +a_{ ip}b_{ pj}$$.
When multiple matrices are multiplied by each other, the number of multiplications required by different calculation order is different. For example, $$a $$is the matrix of $$50 times 10 $, $$B $$is the matrix of $$10 times 20 $, $$C $$is the matrix of $$20 times 5 $,
There are two ways to calculate $$ABC $$: $(AB) C $$and $$a (BC) $. The former requires 15000 times of multiplication, while the latter only requires 3500 times.
Let $$a_ 1,A_ 2,...,A_ N $$is a matrix sequence, $$a_ I $$is of order $$P_{ i-1}*P_ The matrix of I $$$(1 / Leq I / Leq n) $$. Try to determine the multiplication order of the matrix so that $$a is calculated_ 1A_ 2...A_ In the N $$process, the total number of times elements are multiplied is the least.
###Input format:
Each input file is a test case. The first line of each test case gives a positive integer $$n (1 / Leq n / Leq 100) $$, which means there are a total of $$n $$matrices $$a_ 1,A_ 2,..., A_ N $$, the second line gives $$n + 1 $$integers $$P_ 0,P_ 1...P_ N $$, separated by spaces, where $$1 \ \ Leq p_ I / Leq 100 (0 / Leq I / Leq n) $$, the $$I $$th matrix $$a_ I $$is of order $$P_{ i-1}*P_ The matrix of I $$.
###Output format:
The minimum number of multiplications required to obtain the product of the above matrices.
###Input example:
Here is a set of inputs. For example:
```in
five
30 35 15 5 10 20
```
###Output example:
The corresponding output is given here. For example:
```out
eleven thousand eight hundred and seventy-five
```
answer：If there is no answer, please comment
When multiple matrices are multiplied by each other, the number of multiplications required by different calculation order is different. For example, $$a $$is the matrix of $$50 times 10 $, $$B $$is the matrix of $$10 times 20 $, $$C $$is the matrix of $$20 times 5 $,
There are two ways to calculate $$ABC $$: $(AB) C $$and $$a (BC) $. The former requires 15000 times of multiplication, while the latter only requires 3500 times.
Let $$a_ 1,A_ 2,...,A_ N $$is a matrix sequence, $$a_ I $$is of order $$P_{ i-1}*P_ The matrix of I $$$(1 / Leq I / Leq n) $$. Try to determine the multiplication order of the matrix so that $$a is calculated_ 1A_ 2...A_ In the N $$process, the total number of times elements are multiplied is the least.
###Input format:
Each input file is a test case. The first line of each test case gives a positive integer $$n (1 / Leq n / Leq 100) $$, which means there are a total of $$n $$matrices $$a_ 1,A_ 2,..., A_ N $$, the second line gives $$n + 1 $$integers $$P_ 0,P_ 1...P_ N $$, separated by spaces, where $$1 \ \ Leq p_ I / Leq 100 (0 / Leq I / Leq n) $$, the $$I $$th matrix $$a_ I $$is of order $$P_{ i-1}*P_ The matrix of I $$.
###Output format:
The minimum number of multiplications required to obtain the product of the above matrices.
###Input example:
Here is a set of inputs. For example:
```in
five
30 35 15 5 10 20
```
###Output example:
The corresponding output is given here. For example:
```out
eleven thousand eight hundred and seventy-five
```
answer：If there is no answer, please comment