Cod sursa(job #649838)
#include "stdio.h"
const long INF=666666666666666LL;
const int MAXN = 1024;
typedef long long LLong;
LLong Min(LLong a, LLong b){
if(a<b)
return a;
return b;
}
int main(){
FILE *f;
LLong M[MAXN][MAXN],d[MAXN];
LLong n;
int i,j,k,m;
f = fopen("podm.in","r");
fscanf(f,"%Ld",&n);
for(i=0;i<=n;++i)
fscanf(f,"%Ld",&d[i]);
fclose(f);
for(i=1;i<=n;++i)
M[i][i] = 0;
for(i=1;i<=n-1;++i)
M[i][i+1] = d[i-1]*d[i]*d[i+1];
for(i=2;i<=n-1;++i)
for(j=1;j<=n-i;++j){
m = j+i;
M[j][m] = INF;
for(k=j;k<=m-1;++k)
M[j][m] = Min(M[j][m],M[j][k] + M[k+1][m] + d[j-1]*d[k]*d[m]);
}
f = fopen("podm.out","w");
fprintf(f,"%Ld \n",M[1][n]);
fclose(f);
return 0;
}