题目描述:
给定n个矩阵{A0,A1,…,An-1}, 其中Ai,i=0,…,n-1的维数为pi*pi+1,并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1…An-1,由于矩阵乘法满足结合律,所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序,使得按照这一次序计算矩阵连乘积,需要的“数乘”次数最少。
输入: 第一行输入n的值,第二行输入n个矩阵的维数pi(i=0,…,n)。
输出: 最少乘法次数。
样例输入:
6
30 35 15 5 10 20 25
样例输出:
15125
思路:
代码:
#include<iostream>
using namespace std;
int s[10][10]={0};
//构造最优解
void Traceback(int i,int j){
if(i==j){
cout<<'A'<<i;return;
}
if(i<s[i][j]) cout<<'(';
Traceback(i,s[i][j]);
if(i<s[i][j]) cout<<')';
if(s[i][j]+1<j) cout<<'(';
Traceback(s[i][j]+1,j);
if(s[i][j]+1<j) cout<<')';
}
int main(){
int n,i,j,r,k;
cin>>n;
int p[n+1] = {0},m[n][n]={0};
for(i=0;i<n+1;i++){
cin>>p[i];
}
for(i=0;i<n;i++){
m[i][i]=0;
}
for(r=2;r<=n;r++){
for(i=0;i<=n-r;i++){
j=i+r-1; //i
m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; //m[i][j]初值
s[i][j]=i;
//求最小值
for(k=i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if(t<m[i][j]){
m[i][j]=t;
s[i][j]=k;
}
}
}
}
cout<<m[0][n-1]<<endl;
cout<<'(';
Traceback(0,n-1);
cout<<')';
cout<<endl;
return 0;
}