Умножение матриц
Даны
n матриц с размерами соответственно. Матрицы расположены слева направо в порядке от 1 до n. Разрешается расставлять скобки, чтобы менять порядок умножений.Каково минимальное число операций, необходимое, чтобы перемножить все эти матрицы?
💡
При умножении матрицы на матрицу , выполняется операций.
Входные данные
В первой строке содержится одно целое число
n ().В следующих
n строках заданы размеры матриц (1 ≤ ≤ 1000).Гарантируется, что для .
Выходные данные
Программа должна вывести минимальное число операций, необходимое для умножения всех матриц.
Примеры
Входные данные | Выходные данные |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB