Cod sursa(job #785359)
#include <fstream>
using namespace std;
typedef long long i64;
const int Maxn = 505;
const i64 oo = ( 1LL )<< 60;
i64 Best[Maxn][Maxn], A[Maxn];
int N;
ifstream F("podm.in");
ofstream G("podm.out");
#define min(a, b) ((a) < (b) ? (a) : (b))
int main(void)
{
F>>N;
for (int i=0;i<=N;++i)
F>>A[i];
for (int i=0;i<=N;++i) Best[i][i] = 0;
for (int i=1;i<N;++i) Best[i][i + 1] = A[i - 1] * A[i] * A[i + 1];
for (int w=2;w<N;++w)
for (int i=1;i<=N-w;++i)
{ int j = i + w;
Best[i][j] = oo;
for (int k=i;k<j;++k)
Best[i][j] = min(Best[i][j], Best[i][k] + Best[k + 1][j] + A[i - 1] * A[k] * A[j]);
}
G<<Best[1][N]<<'\n';
}