Multiplicaciones de Matrices
Dadas
n matrices con dimensiones , respectivamente. Las matrices están dispuestas de izquierda a derecha, desde 1 hasta n. Se permite colocar paréntesis para dar prioridad a algunas multiplicaciones.¿Cuál es el número mínimo de operaciones necesarias para multiplicar todas las matrices?
💡
Cuando se multiplica una matriz de tamaño por otra de tamaño , se llevan a cabo operaciones.
Entrada
La primera línea contiene un único entero
n ().Las siguientes
n líneas contienen las dimensiones de cada una de las matrices (1 ≤ ≤ 1000).Se garantiza que para .
Salida
El programa debe imprimir la cantidad mínima de operaciones requeridas para multiplicar todas las matrices.
Ejemplos
Entrada | Salida |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB