/*----------------------------文件頭--------------------------------
  作者:林斌
  Email:lbfjfz@tom.com
  作業名稱：矩陣連乘問題
  
  問    題：矩陣連乘問題
  描    述：給定n 個矩陣｛A1, A2,...,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。
            考察這n個矩陣的連乘積A1A2...An。矩陣A 和B 可乘的條件是矩陣A的列數
  	        等于矩陣B 的行數。若A 是一個p x q矩陣，B是一個q * r矩陣，則其乘積C=AB
	        是一個p * r矩陣,需要pqr次數乘。
        
	        矩陣連乘積的最優計算次序問題，即對于給定的相繼n 個矩陣{A1,A2,...,An}
		    (其中矩陣Ai的維數為 pi-1 * pi，i=1，2，…，n)，確定計算矩陣連乘積
		    A1A2...An 的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。

  編程任務：對于給定的相繼n個矩陣{A1, A2, ..., An }及其維數，編程計算矩陣連
            乘積A1A2...An 需要的最少數乘次數。
  數據輸入：由文件input.txt 給出輸入數據。第1 行是給定的正整數n，表示有n 個矩陣
            連乘。第2行是n+1個正整數P0 , P1, ..., Pn ，表示矩陣Ai 的維數
	   	    為pi-1 * pi ，i=1，2，…，n。
  結果輸出：將計算出的最少數乘次數輸出到文件output.txt。

-------------------------------------------------------------------*/

#include <iostream.h> 
#include <fstream.h>
#include <stdio.h> 


//--------------------- 變量、函數定義 開始 ------------------

ofstream myoutf("output.txt");            //輸出到文件,全局變量


/*----------------- MatrixChain函數定義 ----------------------
 *  函 數 名: MatrixChain                                    *
 *  返回類型: void 無返回值                                  *
 *  參數說明: p[] 矩陣的維數                                 *
 *            n   矩陣連乘的個數                             *
 *			  m   保存矩陣最少連乘個數的二維數組             *
 *  功    能: 輸出 n個矩陣連乘的最優值                       *
 *  調用示例: MatrixChain(p,n,m);                            *
 *-----------------------------------------------------------*/

void MatrixChain(int * p,int n,int * * m);

//--------------------- 變量、函數定義 結束 ------------------



//--------------------- 主函數 開始 --------------------------
void main()
{
  int MatrixNum;                              //定義連乘的矩陣數
  int i , j;
  int * p;
  int * * m;                                  //保存最優值數組

  ifstream myinf("input.txt",ios::nocreate);  //讀取文件
  if (myinf.fail())
  {
  	cerr << "讀入文件時，出錯！";
  	return;                                   //如果沒有輸入文件，則返回錯誤
  }//if (myinf.fail()) 
  
  myinf >> MatrixNum;                         //讀取矩陣個數
  cout << MatrixNum << endl;
  
  if (MatrixNum <= 0)
  {
    cerr << "矩陣連乘個數不合法，出錯！";
    return;                       //如果沒有輸入文件，則返回錯誤
  }// if (MatrixNum > 0)
  
  p = new int[MatrixNum + 1];     //分配矩陣維數數組空間
  if (p == NULL)
  {
    cerr << "數組空間分配不成功，出錯！";
	return;
  }// if (p != NULL) 
 
  for (i = 0;i < MatrixNum +1 ; i++)//讀入矩陣維數
  {
  	myinf >> p[i];
  	cout << p[i] << " ";
  }//for i <= MatrixNum
  cout << endl;

  //----------- 定義二維動態數組 開始 --------------
  
  m = new int * [MatrixNum + 1];      //給一維數組動態分配內存
  for (i=0 ; i < MatrixNum +1; i++)
  { 
	m[i] = new int[MatrixNum +1];
  }//for 分配二維數組空間

  for (i=0 ; i < MatrixNum + 1;i++)   //給數組初始化
    for (j = 0; j < MatrixNum +1;j++)
	{
      m[i][j] = 0;
	}//for 
  //----------- 定義二維動態數組 結束 --------------
    
  MatrixChain(p,MatrixNum, m);       //調用動態規劃矩陣連乘算法

  //--------釋放數組---------
  for(i=0;i < MatrixNum +1 ; i++) delete[] m[i];

  delete[] m;                        //釋放二維數組空間
  
  delete[] p;                        //釋放矩陣維數數組空間
  myinf.close();                     //關閉輸入文件
  myoutf.close();                    //關閉輸出文件
}//void main()

//--------------------- 主函數 結束 --------------------------


/*----------------- move函數定義 ----------------------
  函 數 名: MatrixChain
  返回類型: void 無返回值
  參數說明: 
  功    能: 
  調用示例: 

  編程思路:

  1、分析最優的結構

  將矩陣連乘積Ai,Ai+1,…,Aj簡記為Ai…j。我們來看計算A1…n的一個最優次序。
  設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1 <= k < n，則完全加括號
  方式為((A1…Ak)(Ak+1…An))。照此，我們要先計算A1…k和Ak+1…n，然后，
  將所得的結果相乘才得到A1…n。顯然其總計算量為計算A1…k的計算量加上
  計算Ak+1…n的計算量，再加上A1…k與Ak+1…n相乘的計算量。

  2、建立遞歸關系
  對于矩陣連乘積的最優計算次序問題，設計算Ai…j ,1≤i≤j≤n，所需的最少數
  乘次數為m[i,j]，原問題的最優值為m[1,n]。

  當i=j時，Ai…j=Ai為單一矩陣，無需計算，因此m[i,i]=0，i=1,2,…,n ； 

  當i<j時，可利用最優子結構性質來計算m[i,j]。事實上，若計算Ai…j的最優次序
  在Ak和Ak+1之間斷開，i≤k<j，則：m[i,j]=m[i,k]+m[k+1,j]+pi-1*pk*pj 

  3、計算最優值
  用動態規劃算法解此問題，可依據遞歸式(2.1)以自底向上的方式進行計算，在計算
  過程中，保存已解決的子問題答案，每個子問題只計算一次，而在后面需要時只要
  簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法。下面所給出
  的計算m[i,j]動態規劃算法中，輸入是序列P={p0,p1,…,pn}，輸出除了最優值
  m[i,j]外，還有使m[i,j] = m[i,k] + m[k+1,j] + pi-1*pk*pj達到最優的斷開位置
  k=s[i,j]，1≤i≤j≤n 。



  總    結:
  算法首先設定m[i][i]=0(i=1,2,...,n)。然后再根據遞歸式按矩陣鏈長
  的遞增方式依此計算出各個m[i][j]，在計算某個固定的m[i][j]時，
  只用到已計算出的m[i][k]和m[k+1][j]。


-------------------------------------------------------------*/

void MatrixChain(int * p,int n,int * * m)
{
  for (int i =1; i <= n; i++) m[i][i] = 0;//當i=j時，m[i][j]=0
  for (int r =2; r <= n; r++) 
	for (int i =1; i <= n-r+1; i++)
	{
	  int j = i + r -1;
	  // 因為不知道k的位置，所以m[i][j]遞歸的看作
	  // m[i][i] + m[i+1][j] + p[i-1] * p[i] * p[j];
	  // 然后通過下面的循環，找到k的位置
	  m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];
	  //s[i][j] = i;
      
	  //假設在k位置斷開，然后計算最少乘數，
	  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;
		}//if 
        //=================================================
	  }//for k
	
	}//for i

    myoutf << m[1][n] << endl;            //輸出結果到文件

}//void MatrixChain