e102. Q-6-18. 矩陣乘法鏈 - 花中程式設計挑戰系統

Content

兩個矩陣 A 與 B 要相乘，必須滿足 A 的行數等於 B 的列數，若 A 是 p x q 的矩陣，B 是q x r的矩陣，則A x B的結果是一個p x r的矩陣，而需要的純量乘法數假設是p x q x r。矩陣乘法滿足結合律，也就是說 A x B x C = (A x B) x C = A x (B x C)，可是不同順序所需要的純量乘法數不同。輸入 p[0], p[1], …, p[n]，代表有 n 個矩陣相乘的乘法鏈，而它們的矩陣的大小依序分別是 p[0] x p[1]、p[1] x p[2]、…、 p[n-1] x p[n]，請找出最好的相乘順序使得使用的純量乘法數的總和最少。

舉例來說，n=3，矩陣大小為，A1: 3 x 5, A2: 5 x 4, A3: 4 x 2

乘法順序為(A1 x A2) x A3 時，乘法數 3 * 5 * 4 + 3 * 4 * 2 = 84；若乘法順序為 A1 x (A2 x A3)時，乘法數 3 * 5 * 2 + 5 * 4 * 2 = 70。最少的純量乘法數為 70。

Time limit: 1 秒

Input

第一行是正整數 n。第二行有 n+1 個正整數， p[0] ~ p[n]，數字間以空白隔開。n <= 200，p[i] <= 200。

Output

最小的純量乘法數量。

Sample Input

範例一：
3
3 5 4 2

範例二：
4
5 1 3 4 2

Sample Output

範例一：
70

範例二：
30

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

Tags:

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」