d086: Q-6-18. 矩陣乘法鏈
Tags : DP
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

Content

兩個矩陣 A 與 B 要相乘,必須滿足 A 的行數等於 B 的列數,若 A 是 p*q 的矩陣,B

是q*r的矩陣,則A*B的結果是一個p*r的矩陣,而需要的純量乘法數假設是p*q*r。

矩陣乘法滿足結合律,也就是說 A*B*C = (A*B)*C = A*(B*C),可是不同順序所

需要的純量乘法數不同。輸入 p[0], p[1], …, p[n],代表有 n 個矩陣相乘的乘

法鏈,而它們的矩陣的大小依序分別是 p[0]*p[1]、p[1]*p[2]、…、 p[n-1]*p[n],請找出最好的相乘順序使得使用的純量乘法數的總和最少。

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

乘法順序為(A1* A2)*A3 時,乘法數 3 * 5 * 4 + 3 * 4 * 2 = 84;

若乘法順序為 A1*(A2 *A3)時,乘法數 3 * 5 * 2 + 5 * 4 * 2 = 70。

最少的純量乘法數為 70。

Input

第一行是正整數 n。第二行有 n+1 個正整數, p[0] ~ p[n],數字間以

空白隔開。n <= 200,p[i] <= 200

Output

最小的純量乘法數量。

Sample Input
// 1
3
3 5 4 2
// 2
4
5 1 3 4 2
Sample Output
// 1
70
// 2
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:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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