program Soucin_Matic_Dynamicky;
{Metodu dynamickeho programovani urcuje minimalni pocet
nasobeni potrebny k vynasobeni N obdelnikovych matic.
Vstupem programu jsou rozmery matic.}

const MaxN = 100;   {maximalni pocet nasobenych matic}

var P: array[0..MaxN] of integer;
      {rozmery matic -> i-ta matice ma velikost P[i-1]xP[i]}
    M: array[1..MaxN,1..MaxN] of integer;
    N: integer;         {pocet matic}
    Poc: integer;       {k vypoctu poctu nasobeni}
    Min: integer;       {minimalni pocet nasobeni}
    i,j,k: integer;

begin
writeln('Zadejte rozmery nasobenych matic:');
i:=0;
while not eof do
  begin read(P[i]); i:=i+1 end;
N:=i-1;                 {pocet matic}

for j:=1 to N do M[1,j]:=0;
for i:=2 to N do        {radky matice M}
  for j:=1 to N-i+1 do
    begin
    Min:=maxint;
    for k:=1 to i-1 do
      begin
      Poc:=M[K,j] + M[i-k,j+k]          {nasobeni v usecich}
           + P[j-1] * P[j+k-1] * P[j+i-1];
                                        {posledni nasobeni}
      if Poc < Min then Min:=Poc
      end;
    M[i,j]:=Min
    end;

writeln('Minimalni pocet nasobeni: ', M[N,1])
end.