Moltiplicazioni di Matrici
Date
n matrici con dimensioni , rispettivamente. Le matrici sono ordinate da sinistra a destra, dalla 1 alla n. È consentito inserire parentesi per scegliere l’ordine in cui eseguire alcune moltiplicazioni.Qual è il numero minimo di operazioni necessario per moltiplicare tutte le matrici?
💡
Quando si moltiplica una matrice per una matrice , vengono eseguite operazioni.
Input
La prima riga contiene un singolo intero
n ().Le successive
n righe contengono le dimensioni di ciascuna matrice (1 ≤ ≤ 1000).È garantito che per .
Output
Il programma deve stampare il numero minimo di operazioni richieste per moltiplicare tutte le matrici.
Esempi
Input | Output |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB