Cod sursa(job #515656)
#include <fstream>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
const int maxn=505; const long long INF=100000000000000000LL;
int i,j,q,k,N;
long long best[maxn][maxn], d[maxn];
int Min(long long a,long long b)
{
if(a<b) return a;
return b;
}
int main()
{
fin >> N;
for(i=1;i<=N+1;i++)
fin >> d[i-1];
for(i=1;i<=N;i++) best[i][i]=0;
for(i=1;i<=N;i++) best[i][i+1]=d[i-1]*d[i]*d[i+1];
for(q=2;q<=N-1;q++) // distanta --> best[i][i+q]
for(i=1;i<=N-q;i++) // parcurgerea matricelor pe portiuni q
{
j=i+q; //ultima matrice
best[i][j]=INF;
for(k=i;k<=j-1;k++)
best[i][j]=Min(best[i][j],best[i][k]+best[k+1][j]+d[i-1]*d[k]*d[j]);
}
fout << best[1][N];
}