\(N\) 개의 행렬 \(A_1, A_2, \dots, A_N\) 을 순서대로 곱하려고 합니다. 행렬 \(A_k\) 의 크기는 \(p_{k-1} \times p_k\) 입니다. 즉 차원 수열 \(p_0, p_1, \dots, p_N\) 이 주어집니다.

\(a \times b\) 행렬과 \(b \times c\) 행렬을 곱하는 데 드는 비용을 \(a \cdot b \cdot c\) 라고 할 때, 곱셈을 묶는 순서(괄호 치는 방법)를 잘 정하여 전체 곱셈 비용의 합을 최소로 만드는 값을 구하세요.

전형적인 행렬 곱셈 순서(matrix chain) 문제로, \(O(N^3)\) 구간 DP로 해결합니다.

• \(1 \le N \le 300\)
• \(1 \le p_i \le 500\)

첫 줄에 행렬의 개수 \(N\) 이 주어집니다.

둘째 줄에 \(N+1\) 개의 정수 \(p_0, p_1, \dots, p_N\) 이 주어집니다.

최소 곱셈 비용을 한 줄에 출력합니다.

riseoj 작성

출처 Original