[mc*] Optymalne nawiasowanie (*)
Języki:
cpp
Limit czasu: 5.0 s
Limit pamięci: 10 MB
Limit rozmiaru rozwiązania: 30 kB
Zadanie dodatkowe!
Przykładowe wejście I
Wynik I
Przykładowe wejście II
Wynik II
Problem
Wyznaczenie optymalnego nawiasowanie ciągu macierzy oraz kosztu tego nawiasowania (liczbę mnożeń skalarnych potrzebnych do wymnożenia ciągu macierzy wg optymalnego nawiasowania). Użyj programowania dynamicznego.
Wejście
W pierwszej linii liczba naturalna 0 < n <= 100 = liczba macierzy.
W kolejnych n+1 liniach rozmiary p[0], p[1],...p[n]
(tj. i-ta macierz ma rozmiar p[i-1]xp[i]).
Wyjście
W pierwszej linii koszt optymalnego nawiasowania.
W drugiej linii napis przedstawiający optymalne nawiasowanie. i-tą macierz wypisujemy jako Ai, mnożenie zapisujemy bez kropki (tj. iloczyn macierzy Ai oraz Aj jako AiAj). Nawiasy okrągłe.
Przykładowe wejście I
3
10
100
5
50
Wynik I
7500
(A1A2)A3
Przykładowe wejście II
12
10
20
3
14
5
8
19
22
3
10
11
100
5
Wynik II
8010
(A1A2)(((A3A4)(A5(A6(A7A8))))(((A9A10)A11)A12))
