Multiplicação de Matrizes
Dadas
n matrizes com dimensões , respetivamente. As matrizes estão ordenadas da esquerda para a direita, de 1 a n. É permitido colocar parênteses para dar prioridade a algumas multiplicações.Qual é o número mínimo de operações necessárias para multiplicar todas as matrizes?
💡
Ao multiplicar uma matriz por uma matriz , realizam-se operações.
Entrada
A primeira linha contém um único número inteiro
n ().As próximas
n linhas contêm as dimensões de cada uma das matrizes (1 ≤ ≤ 1000).Garante-se que para .
Saída
O programa deve imprimir o número mínimo de operações necessárias para multiplicar todas as matrizes.
Exemplos
Entrada | Saída |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB