/*
Enunt:
Parantezare optima de matrici
Se dă un produs matricial M = M1M2...Mn. Cum înmulţirea matricelor este asociativă, toate parantezările conduc la acelaşi rezultat. Însă, numărul total de înmulţiri scalare al produsului matricial poate să difere substanţial în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor n matrici se dau sub forma unui şir d astfel încât perechea (di-1, di) reprezintă dimensiunile matricii Mi.

Cerinţă
Se cere să se minimizeze numărul total de înmulţiri scalare al produsului matricial M, valoare ce corespunde unei parantezări optime.

Date de intrare
Fişierul de intrare podm.in conţine pe prima linie un număr natural n, reprezentând numărul matricelor. Pe următoarea linie se găsesc n + 1 numere naturale, reprezentând valorile şirului d.

Date de ieşire
În fişierul de ieşire podm.out se va găsi un singur număr natural egal cu valoarea minimă a numărului total de înmulţiri scalare a produsului matricial M.

Restricţii
1 ≤ n ≤ 500
1 ≤ di ≤ 10 000, unde 0 ≤ i ≤ n
Exemplu

podm.in	
4
13 5 89 3 34

podm.out
2856

Explicaţie
În exemplu se dau 4 matrici: A de dimensiuni (13, 5), B de (5, 89), C de (89, 3), D de (3, 34). În funcţie de ordinea efectuării înmulţirilor matriciale , numărul total de înmulţiri scalare poate să fie foarte diferit:

(((AB)C)D) : 10582 înmulţiri
((AB)(CD)) : 54201 înmulţiri
((A(BC))D) : 2856 înmulţiri
(A((BC)D)) : 4055 înmulţiri
...
Rezultatul optim se obţine pentru cea de a treia parantezare: ((A(BC))D).
*/

/*
Rezolvare:

a[i][j] = costul minim ptr produsul de la i->j
ptr orice k de la (i) -> (j-1) a[i][j] = min(a[i][k] + a[k+1][j] + x[i-1] * x[k] * x[j])

*/


#include <stdio.h>

FILE *in, *out;
int n, x[501], a[501][501];

int main ()
{
	int i, j, k, v, vmin;
	in = fopen("podm.in", "r");
	out = fopen("podm.out", "w");

	fscanf(in, "%d", &n);

	for (i=0; i<=n; i++)
	{
		fscanf(in, "%d", &x[i]);
	}

	// matricea i are dim x[i-1] si x[i];
	for (i=1; i<n; i++)
	{
		a[i][i+1] = x[i-1] * x[i] * x[i+1];
	}

	for (k=2; k<=n-1; k++)
	{
		for (i=1; i+k<=n; i++)
		{
			// Calculam pe primul
			vmin = a[i][i] + a[i+1][i+k] + x[i-1] * x[i] * x[i+k];

			// Aflam minimul
			for (j=i+1; j<i+k; j++)
			{
				v = a[i][j] + a[j+1][i+k] + x[i-1] * x[j] * x[i+k];
				if (v < vmin)
				{
					vmin = v;
				}
			}

			// Pastram minimul
			a[i][i+k] = vmin;
		}
	}

	/*for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
		{
			fprintf(out, "%6d ", a[i][j]);
		}
		fprintf(out, "\n");
	}*/

	fprintf(out, "%d\n", a[1][n]);

	fclose(out);
	fclose(in);

	return 0;
}