#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <string.h> #include <stdio.h> using namespace std; #define MAXINT 0x7FFFFFFF int main() { int N, a[100]; int matrix[100][100]; while (cin >> N) { for (int i = 0; i < N; i++) cin >> a[i]; memset(matrix, 0, sizeof(matrix)); int dist = 2; while (dist < N) { for (int i = 0; i + dist < N; i++) { int min = MAXINT; for (int j = i + 1; j <= i + dist - 1; j++) {int tmp = matrix[i][j] + matrix[j][i + dist] + a[i] * a[j] * a[i + dist];if (tmp < min) min = tmp; } matrix[i][i + dist] = min; } dist++; } cout << matrix[0][N - 1] << endl; } }
