#include <iostream> #include <stdio.h>#include <assert.h>#include <stdlib.h>#include <String.h>#define MAX 100typedef struct Matrix{ int left; int right;}Matrix;using namespace std;//自底向上的矩阵链乘法 void MATRIX_CHAIN_ORDER(Matrix a[], int num){ //创建存储最优子问题解的数组 int m[MAX][MAX], s[MAX][MAX]; //数组初始化 memset(m, MAX*MAX, sizeof(int)); memset(s, MAX*MAX, sizeof(int)); for(int i=0; i<num; i++) m[i][i] = 0; for(int l=2; l<=num; l++){ for(int i=0; i<num-1; i++){ //依次计算计算链长为l的最小矩阵乘积 int j = i+l-1; m[i][j] = 2e31; for(int k=i; k<=j-1; k++){ int i_j_sum = m[i][k]+m[k+1][j]+a[i].left*a[k].right*a[j].right; if(i_j_sum<m[i][j]){ m[i][j] = i_j_sum; s[i][j] = k; } } } for(int i=0; i<num; i++){ for(int j=0; j<num; j++){ cout <<m[i][j]<<" "; } cout<<endl; } } cout<<m[0][num-1]; return;}int LOOKUP_CHAIN(int m[][MAX], Matrix a[], int i, int j){ if(i == j){ m[i][j]=0; } for(int k=i; k<j; k++){ int q = LOOKUP_CHAIN(m, a, i, k)+LOOKUP_CHAIN(m, a, k+1, j) + a[i].left*a[k].right*a[j].right; if(q<m[i][j]){ m[i][j] = q; } } return m[i][j];} //自顶向下的矩阵链乘法 void MEMOIZED_MATRIX_CHAIN(Matrix a[], int num){ //创建存储最优子问题解的数组 int m[MAX][MAX], s[MAX][MAX]; //数组初始化 memset(m, MAX*MAX, sizeof(int)); memset(s, MAX*MAX, sizeof(int)); for(int i=0; i<num; i++){ for(int j=i; j<num; j++){ m[i][j] = 2e31; } } //递归计算 LOOKUP_CHAIN(m, a, 0, num-1); cout<<m[0][num-1]; return;}int main(){ Matrix a[MAX]; int num = -1; while(cin>>num){ //输入矩阵参数 for(int i=0; i<num; i++) cin>>a[i].left>>a[i].right; // MATRIX_CHAIN_ORDER(a, num); MEMOIZED_MATRIX_CHAIN(a, num); } return 0; }
