P1753 Matrix Chain Ordering Problem

Given $n$ matrices, the $i$-th matrix $M_i$ has size $w_i$ rows and $w_{i+1}$ columns, and we do not care about their contents. We consider multiplying them in order (called the chain product): $$ M = M_1 \times M_2 \times \cdots \times M_n $$ Matrix multiplication is not commutative, but it is associative. Therefore, by choosing a good order of association, we can reduce the number of operations as much as possible. In this problem, we define that multiplying a matrix of size $a \times b$ by a matrix of size $b \times c$ requires $abc$ operations. Please compute the minimum number of operations needed to compute the chain product of the given $n$ matrices. For convenience, you do not need to construct the optimal order.

The first line contains a positive integer $n$, representing the number of matrices. The next line contains $n+1$ positive integers. The $i$-th integer is $w_i$, with the meaning described above.

Output one integer, representing the minimum number of operations.

Sample explanation: The sample tells us that there are $n = 3$ matrices, with sizes $5 \times 3$, $3 \times 2$, and $2 \times 6$. Consider the two possible multiplication orders: - Multiply $M_1$ and $M_2$ first to get a $5 \times 2$ matrix, then multiply it by $M_3$. The number of operations is $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$. - Multiply $M_2$ and $M_3$ first to get a $3 \times 6$ matrix, then multiply it by $M_1$. The number of operations is $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$. This problem asks for the minimum number of operations, so the answer is $90$. --- Constraints: For all testdata, $1 \leq n \leq 2 \times 10^6$, $1 \leq w \leq 10^4$. Specifically: - For $30\%$ of the testdata, $n \leq 500$. - For another $30\%$ of the testdata, $n \leq 2 \times 10^5$. # Input Format {{formatI}} # Output Format {{formatO}} # Hint {{hint}} Translated by ChatGPT 5