時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
給定矩陣尺寸及已完全加括號的乘法運算式，計算依指定順序相乘所需的純量乘法次數，不要求最佳化順序。r × k 矩陣乘 k × c 矩陣需要 rkc 次純量乘法，結果為 r × c；若前者欄數與後者列數不同，運算無法進行。
輸入格式
第一行 n（1 ≤ n ≤ 26），接著 n 行各含一個大寫字母矩陣名、列數及欄數。之後每行一個運算式，讀至檔案結尾。運算式為單一矩陣名，或以括號包住兩個相接的運算式，乘號省略。
輸出格式
每個運算式輸出一行：尺寸不相容輸出 error，否則輸出總純量乘法次數。單獨一個矩陣需要 0 次乘法。
題目來源：UVa 442 — Matrix Chain Multiplication，CPE 歷屆試題。 原題：https://onlinejudge.org/external/4/442.pdf
範例測資
範例輸入 1
9 A 50 10 B 10 20 C 20 5 D 30 35 E 35 15 F 15 5 G 5 10 H 10 20 I 20 25 A B C (AA) (AB) (AC) (A(BC)) ((AB)C) (((((DE)F)G)H)I) (D(E(F(G(HI))))) ((D(EF))((GH)I))
範例輸出 1
0 0 0 error 10000 error 3500 15000 40500 47500 15125
請先登入後再提交程式碼
討論與題解
載入討論區…