Cod sursa(job #651272)
#include<stdio.h>
#define MAX 100000000000000000LL
long long min(int a,int b)
{
return a<b ? a : b;
}
int main()
{
FILE *fin,*fout;
fin=fopen("podm.in","r");
fout=fopen("podm,out","w");
int N,dim[506],i,j,d,k;
long long M[505][505];
fscanf(fin,"%d",&N);
for(i=0;i<=N;i++)
fscanf(fin,"%d",&dim[i]);
for(i=1;i<=N;i++)
M[i][i]=0;
for(d=1;d<N;d++)
{
for(i=1;i<=N-d;i++)
{
M[i][i+d]=MAX;
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(fout,"%lld",M[1][N]);
fclose(fin);
fclose(fout);
return 0;
}