行列の積
n 個の行列 が与えられており、それぞれのサイズは です。行列は左から右へ 1 から n の順に並んでいて、どのように括弧を配置して掛け合わせるかは自由に決められます。すべての行列を掛け合わせるために必要な演算回数の最小値を求めてください。
💡
行列 を の行列と掛け合わせる場合、 回の演算が必要になります。
入力
最初の行には整数
n () が 1 つ与えられます。続く
n 行には、それぞれの行列の次元 (1 ≤ ≤ 1000) が与えられます。また、 に対して が保証されています。
出力
すべての行列を掛け合わせるのに必要な演算の最小回数を出力してください。
例
入力 | 出力 |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB