o188.
Q-6-18. 矩陣乘法鏈
內容
兩個矩陣 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
輸出說明
最小的純量乘法數量
範例輸入
#1
3 3 5 4 2
範例輸出
#1
70
範例輸入
#2
4 5 1 3 4 2
範例輸出
#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
公開 測資點#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
提示 ：
標籤:
出處:
ap325
[管理者：
mushroom.cs9
...
(mushroom)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 41558 |
|
o188 | 46 | 2024-08-06 15:03 |