//
// CSC 321, Assignment 4 test program mcotest.cpp
//
// You may use this code to test your implementation of the algorithm
// on p. 336 of the text.
//
// Read the description of the matrix chain order problem and
// solution on pp. 331-338 in the text.  In that description, n is the
// number of matrices in the chain A1, A2, ..., An.  The array p has length 
// n+1 p[i-1] and p[i] are the dimensions of matrix Ai.  The two-dimensional
// table m has size n by n.  
//


#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{
	int n = 6; // n is the number of matrices in the chain
	int **m;   // m is an n-by-n table used to find the optimal solution
	int **s;   // s is an n-by-n table used to keep track of where
	           //   parentheses would be placed.
	int p[] = {30, 35, 15, 5, 10, 20, 25};
	           // The above values were taken from the example in the text.

	// The next six lines allocate memory for m and s, which are both
	// two-dimensional n-by-n tables.
	m = new int*[n+1];
	s = new int*[n+1];

	for (int j = 1; j <= n; j++) {
		m[j] = new int[n+1];
		s[j] = new int[n+1];
	}

	computeOptimalChainOrder(p, m, s, n);

	// Upon returning from computeOptimalChainOrder, the upper triangle of
	// m and the upper triangle minus the diagonal of s have been filled in.
	// Here, we print the contents of m.
	cout << "Matrix m: " << endl;
	for (int i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (j < i)
				cout << setw(6) << " ";
			else
				cout << setw(6) << m[i][j];
		}
		cout << endl;
	}

	// The number of multiplications in the optimal solution is
	// always in m[1][n].  
	cout << "The minimal number of multiplications is " << m[1][n] << endl;

	// Writing a function to print the optimal parenthesization is not
	// necessary but would be a nice touch.
//	cout << "Optimal parenthesization: " << endl;
//	printOptimalParens(s, 1, n);
//	cout << endl;

	return 0;
}