Cod sursa(job #465268)
#include <stdio.h>
using namespace std;
#define INF 9000000
long long m[505][505];
long long p[505], q;
long int n, i, j, k, l;
int main ()
{
FILE *f = fopen ("podm.in","r");
FILE *g = fopen ("podm.out","w");
fscanf (f,"%d", &n);
for (i=1; i<=n+1; ++i)
fscanf (f,"%lld", &p[i]);
for (i=1; i<=n; ++i)
m[i][i] = 0; /* initializam diagonala principala pt matricele de tip Ai..i */
for (l=2; l<=n; ++l)
for (i=1; i<=n-l+1; ++i)
{
j = i + l - 1;
m[i][j] = INF;
for (k=i; k<j; ++k)
{
q = m[i][k] + m[k+1][j] + (p[i] * p[k+1] * p[j+1]);
if (q < m[i][j])
m[i][j] = q;
}
}
fprintf (g,"%lld", m[1][n]);
fclose(g);
fclose(f);
return 0;
}