#include <iostream>
#include <limits.h>

// Матрица Ai имее размерность p[i-1] x p[i] для i = 1..n
int MatrixChainOrder(int p[], int n)
{
    /* Для простоты программы, в m[][] одна дополнительаня строка и
       один дополнительный столбец].  Нулевая строка и нулевой столбец в m[][] не используются */
    int **m = new int* [n];
	for(int i = 0; i < n; i++)
		m[i] = new int [n];

    int i, j, k, L, q;

    /* m[i,j] = минимальное число скалярных умножений, необходимое для вычисления
       матрицы A[i]A[i+1]...A[j] = A[i..j], где размерность A[i] равна
       p[i-1] x p[i] */

    // Стоимость равна нулю, когда умножаем одну матрицу
    for (i = 1; i < n; i++)
        m[i][i] = 0;

    // L - длина цепочки  
    for (L=2; L<n; L++)   
    {
        for (i=1; i<=n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;
            for (k=i; k<=j-1; k++)
            {
                // q = стоимость/скалярные умножения
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }

    return m[1][n-1];
}

int main(){
	const int n = 10;
	int p[n] = {10, 50, 30, 7, 25, 60, 15, 80, 55, 30};
	int cost = 0;

	cost = MatrixChainOrder(p, n - 1);

	//std::cout << "Solution for m and s: " << std::endl;

	std::cout << "min cost: " << cost << std::endl;
	int pause;
	std::cin >> pause;
}