Multiplicació òptima de matrius P11455


Statement
 

pdf   zip

thehtml

Donades dues matrius amb dimensions n1 × n2 i n2 × n3, el cost de l’algorisme habitual per multiplicar-les és Θ(n1 n2 n3). Per senzillesa, considerem que el cost és exactament n1 n2 n3.

Suposem que hem de calcular M1 × … × Mm, on cadascuna de les Mi és una matriu amb dimensions ni × ni+1. Com que el producte de matrius és associatiu, es pot triar en quin ordre es fan les multiplicacions. Per exemple, per calcular M1 × M2 × M3 × M4, es podria fer (M1 × M2) × (M3 × M4), amb cost n1 n2 n3 + n3 n4 n5 + n1 n3 n5, o bé M1 × ((M2 × M3) × M4), amb cost n2 n3 n4 + n2 n4 n5 + n1 n2 n5, o bé tres altres ordres possibles.

Feu un programa que trobi el cost mínim de calcular M1 × … × Mm.

Entrada

L’entrada consisteix en diversos casos, cadascun amb m seguit de les m + 1 dimensions. Suposeu 2 ≤ m ≤ 100 i 1 ≤ ni ≤ 104.

Sortida

Per a cada cas, escriviu el cost mínim de calcular el producte de les m matrius.

Public test cases

  • Input

    2   1 2 3
3   10 20 30 40
10  9000 4000 3500 8000 2000 7500 6000 1000 8500 5500 7000

    Output

    6
18000
302250000000
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++