Se citeste un numar natural n (numarul de varfuri ale unui poligon convex, numerotate de la 0 la n-1 in ordinea de pe contur) si cele n 'ponderi' asociate varfurilor. Impartind poligonul in triunghiuri prin diagonale care nu se intersecteaza , costul unui triunghi format din varfurile i, j, k este produsul ponderilor lor. Determinati, folosind Programarea Dinamica, costul total minim al unei triangulari complete a poligonului.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n ponderi ale varfurilor.
- Date de iesire
- Se afiseaza un singur numar: costul minim total al unei triangulari.
- Restrictii
- 3 <= n <= 100, 1 <= pondere <= 100
Exemple
Exemplul 1
Intrare
4 1 2 3 4
Iesire
18
Exemplul 2
Intrare
3 1 1 1
Iesire
1