Cod sursa(job #761731)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 27 iunie 2012 11:39:17
Problema Parantezare optima de matrici Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.7 kb
Program podm;
const inf=100000000000000;
 var a:array [1..500,1..500] of int64;
     d:array [0..10000] of longint;
     i,j,n,k,w:longint;
     fi,fo:text;
function min(a,b:int64):int64;
begin
 if a<b then min:=a else min:=b;
end;
begin
 assign(fi,'podm.in');
  assign(fo,'podm.out');
 reset(fi); rewrite(fo); readln(fi,n);
  for i:=0 to n do read(fi,d[i]);
   for i:=1 to n-1 do
     a[i,i+1]:=d[i-1]*d[i]*d[i+1];
  for w:=2 to n-1 do
   for i:=1 to n-w do begin
                  j:=i+w;
                  a[i,j]:=inf;
                  for k:=i to j-1 do
                   a[i,j]:=min(a[i,j],a[i,k]+a[k+1,j]+d[i-1]*d[k]*d[j]);
                  end;
   write(fo,a[1,n]);
  close(fo);
end.