o188. Q-6-18. 矩陣乘法鏈
Tags : 區間 dp
Accepted rate : 7人/8人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-07-05 02:50

Content

兩個矩陣 A 與 B 要相乘,必須滿足 A 的行數等於 B 的列數。
A 是 p x q 的矩陣B 是 q x r 的矩陣,則 AxB 的結果是一個 p x r 的矩陣,而需要的純量乘法數則為 pqr


矩陣乘法滿足結合律,也就是 AxBxC = (AxB)xC = Ax(BxC),
對於不同計算順序所需要的純量乘法數不同。


輸入 p[0], p[1], ..., p[n] 代表有 n 個矩陣相乘的乘法鏈,
而它們的矩陣的大小依序是 (p[0]xp[1])、(p[1]xp[2])、...、(p[n-
1]xp[n]),
請找出最好的相乘順序使得使用的純量乘法數的總和最少。

舉例來說,n=3,矩陣大小為 A1: (3 x 5), A2: (5 x 4), A3: (4 x 2)
若乘法順序為 (A1 x A2) x A3,則純量乘法數為 (3 x 5 x 4) + (3 x 4 x 2) = 84
若乘
法順序為 A1 x (A2 x A3),則純量乘法數為 (3 x 5 x 2) + (5 x 4 x 2) = 70。
因此最少的
純量乘法數為 70。

Input

第一行是正整數 n。
第二行有 n+1 個正整數 p[0], p[1], ..., p[n] 數字間以空白隔開。
n ≤ 200, p[i] ≤ 200

Output

最小的純量乘法數量

Sample Input #1
3
3 5 4 2
Sample Output #1
70
Sample Input #2
4
5 1 3 4 2
Sample Output #2
30
測資資訊:
記憶體限制: 512 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 [管理者: mushroom.cs9 ... (mushroom) ]

Status Forum 排行

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