Matrixmultiplikationen
Gegeben sind
n Matrizen mit den Abmessungen . Die Matrizen sind von links nach rechts mit den Indizes 1 bis n angeordnet. Es ist erlaubt, Klammern so zu setzen, dass bestimmte Multiplikationen bevorzugt ausgeführt werden.Gesucht ist die minimale Anzahl von Operationen, um alle Matrizen zu multiplizieren.
💡
Beim Multiplizieren einer -Matrix mit einer -Matrix werden Operationen ausgeführt.
Eingabe
Die erste Zeile enthält eine einzelne ganze Zahl
n ().Die folgenden
n Zeilen enthalten die Dimensionen jeder Matrix (1 ≤ ≤ 1000).Es gilt für .
Ausgabe
Das Programm soll die minimale Anzahl an Operationen ausgeben, die erforderlich ist, um alle Matrizen zu multiplizieren.
Beispiele
Input | Output |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB