#include<iostream.h>
#include"make2db.h"
int r[7]={0,10,5,1,10,2,10};
int **kay,**c;
void MatrixChain(int r[],int q,int **c,int **kay)
{ // 為所有的Mij 計算耗費和kay
  // 初始化c[i][i], c[i][i+1]和kay[i][i+1]
	for(int i=1;i<q;i++)
	{
		c[i][i]=0;
		c[i][i+1]=r[i]*r[i+1]*r[i+2];
		kay[i][i+1]=i;
	}
	c[q][q]=0;
	//計算余下的c和kay
	for(int s=2;s<q;s++)
		for(int i=1;i<=q-s;i++)
		{
			// k=i時的最小項
			c[i][i+s]=c[i][i]+c[i+1][i+s]+r[i]*r[i+1]*r[i+s+1];
			kay[i][i+s]=i;
			// 余下的最小項
			for(int k=i+1;k<i+s;k++)
			{
				int t=c[i][k]+c[k+1][i+s]+r[i]*r[k+1]*r[i+s+1];
				if(t<c[i][i+s])
				{ // 更小的最小項
					c[i][i+s]=t;
					kay[i][i+s]=k;
				}
			}
		}
}
void Traceback(int i,int j,int **kay)
{ //輸出計算Mi j 的最優方法
	if(i==j) return;
	Traceback(i,kay[i][j],kay);
	Traceback(kay[i][j]+1,j,kay);
	cout<<"Multiply M"<<i<<","<<kay[i][j];
	cout<<"and M"<<(kay[i][j]+1)<<","<<j<<endl;
}
void main()
{
	int q=5;
	int i,j;
	Make2DArray(c,q+1,q+1);
	Make2DArray(kay,q+1,q+1);
	for(i=1;i<=q;i++)
		for(j=i;j<=q;j++)
			c[i][j]=0;
		cout<<"Optimal cost is"<<c(1,q)<<endl;
		cout<<"kay matrix is"<<endl;
		for(i=1;i<=q;i++)
		{
			for(j=1;j<=i;j++)
				cout<<0<<' ';
			for(j=i+1;j<=q;j++)
				cout<<c[i][j]<<' ';
			cout<<endl;
		}
		cout<<"kay matrix is"<<endl;
		for(i=1;i<=q;i++)
		{
			for(j=1;j<=i;j++)
				cout<<0<<' ';
			for(j=i+1;j<=q;j++)
				cout<<kay[i][j]<<' ';
			cout<<endl;
			Traceback(1,q,kay);
		}
}