兩個矩陣 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。
第一行是正整數 n。
第二行有 n+1 個正整數 p[0], p[1], ..., p[n] 數字間以空白隔開。
n ≤ 200, p[i] ≤ 200
最小的純量乘法數量
3 3 5 4 2
70
4 5 1 3 4 2
30
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
41558 |
|
o188 | 46 | 2024-08-06 15:03 |