행렬 곱셈 순서 2

플래티넘 III

난이도

시간 제한

256MB

메모리 제한

맞았습니다!!

제출 수

0.0%

정답률

레이팅

의견: 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]과 완전히 같은 문제이지만, $$N$$ 이 훨씬 크기 때문에 $$O(N^3)$$ 구간 DP로는 제한 시간 안에 해결할 수 없습니다. $$O(N^2)$$ 이하의 더 빠른 알고리즘(예: 볼록 다각형 삼각분할로 바꾸어 푸는 Hu–Shing 알고리즘)이 필요합니다.

제약

$1 \le N \le 5\,000$
$1 \le p_i \le 1\,000$

입력 형식

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

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

출력 형식

최소 곱셈 비용을 한 줄에 출력합니다. 이 값은 매우 클 수 있으므로 $$64$$ 비트 정수 자료형을 사용해야 합니다.

서브태스크

서브태스크	점수	설명
Subtask 1	15점	$1 \le N \le 300$
Subtask 2	35점	$1 \le N \le 2\,000$
Subtask 3	50점	추가 제한이 없다.

예제 1

입력

3
10 20 30 40

출력

설명

$(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

입력