a493. 矩陣鏈乘積 - 旦旦解題農場

內容

給定$n$個矩陣$M_i$的大小為$r[i] \times c[i]$，求計算所有矩陣相乘$M_1 M_2 ...M_n $最少需要用到多少次乘法(保證所有$c[i]=r[i+1]$)已知$a \times b$ 與 $b \times c$ 的矩陣相乘需要$a \times b \times c$次乘法，並變成$a \times c$的矩陣

輸入說明

單筆測資，輸入共$n+1$行

第一行為一個整數$n$，總共有$n (1 \le n \le 500)$個矩陣

接下來的$n$行每個為第$M_i$個矩陣的$r[i] \times c[i]$

輸出說明

輸出一個整數為最少乘法次數(保證答案小於$10^9$)

範例輸入

#範例輸入1
2
1 2
2 3

#範例輸入2
3
2 3
3 5
5 4

範例輸出

#範例輸出1
6

#範例輸出2
70

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1M

提示：

標籤:

出處:

[管理者：

fdhs105285 (jakao)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」