//矩陣連乘問題(動態規劃)

#include <iostream.h>
#include <iomanip.h>
#define N 6

void Output(int n, int a[N+1][N+1])
{
	for(int i=1; i<n; i++)
	{
		cout<<endl<<setw(8*i-7)<<0;
		for(int j=i+1; j<=n; j++)
			cout<<'\t'<<a[i][j];
	}
	cout<<endl<<setw(8*i-7)<<0<<endl;
}

void MatrixChain(int p[N+1], int n, int m[N+1][N+1], int s[N+1][N+1])
{
	for(int r=2; r<=n; r++)
	{
		for(int i=1; i<=n-r+1; i++)
		{
			int j=i+r-1;
			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
			s[i][j]=i;
			for(int k=i+1; k<j; k++)
			{
				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if (t<m[i][j])
				{
					m[i][j]=t;
					s[i][j]=k;
				}
			}
		}
	}
}

void Traceback(int i, int j, int s[N+1][N+1])
{
	if (i==j) return;
	Traceback(i, s[i][j], s);
	Traceback(s[i][j]+1, j, s);
	cout<<"A("<<i<<","<<s[i][j]<<") & A("<<s[i][j]+1<<","<<j<<")"<<endl;
}

void main()
{
	int p[N+1]={30,35,15,5,10,20,25},m[N+1][N+1]={0}, s[N+1][N+1]={0};
	MatrixChain(p, N, m, s);
	Output(N, m);
	Output(N, s);
	cout<<"Multiplay Order:"<<endl;
	Traceback(1, N, s);
}