행렬 곱셈 순서 3
루비 I의견: 0
\(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\) 라고 할 때, 곱셈을 묶는 순서(괄호 치는 방법)를 잘 정하여 전체 곱셈 비용의 합을 최소로 만드는 값을 구하세요.
- \(1 \le N \le 100\,000\)
- \(1 \le p_i \le 1\,000\)
첫 줄에 행렬의 개수 \(N\) 이 주어집니다.
둘째 줄에 \(N+1\) 개의 정수 \(p_0, p_1, \dots, p_N\) 이 주어집니다.
최소 곱셈 비용을 한 줄에 출력합니다. 이 값은 최대 약 \(10^{14}\) 까지 커질 수 있으므로 반드시 \(64\)비트 정수 자료형을 사용해야 합니다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 | \(1 \le N \le 5\,000\) |
Subtask 2 | 30점 | \(1 \le N \le 50\,000\) |
Subtask 3 | 50점 | 추가 제한이 없다. |
3
10 20 30 4018000\((A_1\ A_2) A_3\) 는 \(10\cdot20\cdot30 + 10\cdot30\cdot40 = 6000+12000=18000\), \(A_1(A_2\ A_3)\) 는 \(20\cdot30\cdot40+10\cdot20\cdot40=24000+8000=32000\). 최소는 \(18000\) 입니다.
2
5 4 6120행렬이 둘뿐이므로 곱셈 순서는 하나, 비용은 \(5\cdot4\cdot6=120\) 입니다.
플래티넘 IIIriseoj 작성
출처 Original
평가 및 의견
행렬 곱셈 순서 3
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
행렬 곱셈 순서 3