Se citeste un numar natural n si n+1 numere p0, p1, ..., pn, reprezentand dimensiunile a n matrice A1, A2, ..., An, unde matricea Ai are pi-1 linii si pi coloane. Determinati, folosind Programarea Dinamica, numarul minim de inmultiri scalare necesare pentru a calcula produsul A1A2...*An, alegand optim ordinea in care se fac inmultirile .
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n+1 valori p0, p1, ..., pn.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de inmultiri scalare.
- Restrictii
- 1 <= n <= 100, 1 <= p[i] <= 500
Exemple
Exemplul 1
Intrare
3 10 30 5 60
Iesire
4500
Exemplul 2
Intrare
1 10 20
Iesire
0