上了大學之後,JOI 君修了一門叫做線性代數的課,裡面常常用到矩陣乘法。
假設有矩陣
那
不只如此,矩陣乘法是有結合律的,也就是說
JOI 君拿到了一份作業,題目如下。
給定
看到之後 JOI 君瑟瑟發抖,因為計算量實在太龐大了。
JOI 君發現,因為結合律的關係,只要改變計算順序就有可能省下一些計算量。
聰明的你,可不可以告訴 JOI 君,在最佳狀況下,需要幾次運算才能得到答案呢?
輸入第一行為一個正整數
接下來一行有
代表說,第
請輸出一行整數代表答案。
TIOJ 1488
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~19 | 無額外限制 | 100 |