Cod sursa(job #650404)
#include<stdlib.h>
#include<stdio.h>
//#include<conio.h>
long long int min(long long int a,long long int b)
{
if(a<b) return a;
return b;
}
int main()
{
FILE *f,*g;
f=fopen("podm.in","r");
g=fopen("podm.out","w");
int dim[501],n,i,j,d,k;
long long int M[501][501],infinit=10000000000000;
fscanf(f,"%d",&n);
for(i=0;i<=n;i++)
fscanf(f,"%d",&dim[i]);
for(i=1;i<=n;i++)
{
M[i][i]=0;
M[i][i+1]=dim[i-1]*dim[i]*dim[i+1];
}
for(i=1;i<n-1;i++)
for(j=i+2;j<=n;j++)
M[i][j]=infinit;
for(d=2;d<n;d++)
for(i=1;i<=n-d;i++)
for(k=i;k<i+d;k++)
M[i][i+d]=min(M[i][i+d],M[i][k]+M[k+1][i+d]+dim[i-1]*dim[k]*dim[i+d]);
fprintf(g,"%lld",M[1][n]);
fclose(f);
fclose(g);
return 0;
}