Multiplication de matrices
Étant donné
n matrices de dimensions respectivement. Les matrices sont ordonnées de gauche à droite de 1 à n. Vous pouvez placer des parenthèses pour prioriser certaines multiplications.Quel est le nombre minimal d’opérations pour multiplier toutes les matrices ?
💡
Lorsque l’on multiplie une matrice par une matrice , on effectue opérations.
Entrée
La première ligne contient un seul entier
n ().Les
n lignes suivantes contiennent les dimensions de chacune des matrices (1 ≤ ≤ 1000).Il est garanti que pour .
Sortie
Le programme doit afficher le nombre minimal d’opérations requis pour multiplier toutes les matrices.
Exemples
Entrée | Sortie |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB