/** 
	Най-бързо верижно умножение на n матрици - m[0], m[1], ..., m[n-1]
	В масива a[n+1] са зададени размерите им: 
		a[0] = m[0].rows
		за i = 1, ..., n-1: a[i] = m[i-1].columns = m[i].rows
		a[n] = m[n-1].columns

	Алгоритъмът е демонстриран и с рекурсивна и с итеративна функция.
	Итеративното изчисление е малко по-бързо откъм реална памет и време.
	И в двата случая обаче алгоритъмът е с асимптотично време O(n^3).
*/

#include <iostream>
#define Inf 2000000000;
using namespace std;

const int n = 10; // за 9 матрици

int a[n] = { 12, 34, 10, 6, 16, 26, 25, 14, 11, 24 };

int memo[n][n];
int p[n][n];

int mcm_rec(int i, int j)
{
	if (i == j) return 0;
	if (memo[i][j] != -1) return memo[i][j];
	int m = Inf;
	for (int k = i; k < j; k++)
	{
		int t = mcm_rec(i, k) + mcm_rec(k + 1, j) + a[i - 1] * a[k] * a[j];
		if (t < m){ m = t; p[i][j] = k; }
	}
	return memo[i][j] = m;
}

int mcm_iter()
{
	for (int i = 0; i < n; i++) memo[i][i] = 0;

	for (int l = 2; l < n; l++) for (int i = 0; i < n - l + 1; i++)
	{
		int j = i + l - 1;
		memo[i][j] = Inf;
		for (int k = i; k < j; k++)
		{
			int t = memo[i][k] + memo[k + 1][j] + a[i - 1] * a[k] * a[j];
			if (t < memo[i][j]){ memo[i][j] = t; p[i][j] = k; }
		}
	}
	return memo[1][n - 1];
}

void show_par(int i, int j)
{
	if (i == j) cout << "m" << i;
	else
	{
		cout << "(";
		show_par(i, p[i][j]);
		show_par(p[i][j] + 1, j);
		cout << ")";
	}
}

int main()
{
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) memo[i][j] = -1;

	//cout << mcm_rec(1, 9) << endl;
	cout << mcm_iter() << endl;
	
	show_par(1, 9);
	
	cout << endl;

	return 0;
}