TopCoder

max

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

63.6% (14/22)

Tags

Description

上了大學之後,JOI 君修了一門叫做線性代數的課,裡面常常用到矩陣乘法。

假設有矩陣 A,B 其中 A 是個 n×m 大小的矩陣,且 B 是個 m×k 大小的矩陣。
AB=CC 是個 n×k 大小的矩陣,並且我們需要做 nmk 那麼多次的運算才能夠算出 C

不只如此,矩陣乘法是有結合律的,也就是說 A(BC)=(AB)C

JOI 君拿到了一份作業,題目如下。
給定 N 個矩陣 A1,A2,,AN 請問 A1A2AN 為多少?
看到之後 JOI 君瑟瑟發抖,因為計算量實在太龐大了。
JOI 君發現,因為結合律的關係,只要改變計算順序就有可能省下一些計算量。
聰明的你,可不可以告訴 JOI 君,在最佳狀況下,需要幾次運算才能得到答案呢?

Input Format

輸入第一行為一個正整數 N(N1000) 代表總共有幾個矩陣。
接下來一行有 N+1 個正整數以一個空白隔開 B1,B2,,BN,BN+1(Bi1000)

代表說,第 i 個矩陣是 Bi×Bi+1 的矩陣。

Output Format

請輸出一行整數代表答案。

Sample Input 1

3
1 4 3 2

Sample Output 1

18

Sample Input 2

10
234 21 232 21 389 232 235 89 19 28 34

Sample Output 2

3612119

Hints

Problem Source

TIOJ 1488

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2