/*********************************************************
programmer: linpder
time:  05.10.22
topic: 動(dòng)態(tài)規(guī)劃－－矩陣相乘。
  動(dòng)態(tài)規(guī)劃的問題還有很多，備忘錄方法，最長公共子序列，
凸多邊形的最優(yōu)三角部分等。
*********************************************************/
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>

#define MAX  32767   //定義一個(gè)最大值

int a[11];   //存儲(chǔ)在連乘時(shí)斷開的位置.

void find(int pos[11][11],int s,int e,int &i)
        //用遞歸算法求出斷開的位置.
{
	int b;
	b=pos[s][e];
	if(b<s)return ;  //如果b的值小于s的，退出
	if(b>e)return ;  //如果b的值大于s的，退出
	if(e==s+1)return ; //如果e只比s大一，退出
	a[i]=b;
	i++;
	
	find(pos,s,b,i);	
	find(pos,b+1,e,i);
}

int main()
{
	int N,p[11];
	int i,j,k,g;
	int temp[11][11],pos[11][11],temp1;

	printf("請輸入相乘矩陣的個(gè)數(shù)(不大于10):"); 
	scanf("%d",&N);   //總共有 N個(gè)矩陣相乘
	printf("輸入 %d 個(gè)整數(shù)表示這 %d 個(gè)矩陣的階數(shù):\n",N+1,N);
	for(i=0;i<=N;i++)
		scanf("%d",&p[i]);  //這N個(gè)矩陣的階數(shù)

	printf("\n計(jì)算得到的結(jié)果為如下所示:\n");
	for(i=1;i<=N;i++)
		temp[i][i]=0; 
	for(g=2;g<=N;g++)
		for(i=1;i<=N-g+1;i++)
		{
			j=i+g-1; 
			temp[i][j]=MAX;
			for(k=i;k<=j-1;k++)  //斷點(diǎn)
			{
				temp1=temp[i][k]+temp[k+1][j]+p[i-1]*p[k]*p[j];
				if(temp1<temp[i][j])
				{
					temp[i][j]=temp1; //保存Ai..j相乘的最優(yōu)值。
					pos[i][j]=k;  //保存矩陣Ai..j的最優(yōu)斷開位置。
				}
			}
        //輸出計(jì)算過程的結(jié)果
			cout<<"temp["<<i<<"]["<<j<<"]="<<setw(5)<<temp[i][j];
			cout<<"        pos["<<i<<"]["<<j<<"]="<<pos[i][j]<<endl;
			if(i==N-g+1)
				cout<<endl;  
		}
	
    i=0;
	find(pos,1,N,i);  //找出每個(gè)斷開位置。

	int n=i;

	printf("輸入的矩陣連乘時(shí)斷開的位置如下:\n");
	for(j=0;j<n;j++)
		printf("%d ",a[j]);

	printf("\n所以我們可以得到加括號后的式子為:(A1*(A2*A3))(A4*(A5*A6))\n");
      //輸入為規(guī)定時(shí)的情況，自己定的 ^_^！

	printf("\n采用動(dòng)態(tài)規(guī)劃算法得出的計(jì)算結(jié)果為: ");
	printf("%d\n",temp[1][N]);

	getch();
	return 0;
}