已知5个矩阵并可连乘,编写程序输出矩阵连乘的最优计算次序。 源代码:

#include<iostream>
using namespace std;
const int MAXN=1e5+5;
int n;
int p[MAXN],dp[MAXN][MAXN],s[MAXN][MAXN];
void print(int l,int r){
if(l==r) cout<<"A"<<l;
else{
cout<<"(";
print(l,s[l][r]);
print(s[l][r]+1,r);
cout<<")";
}
}
int main(){
cin>>n;
for(int i=1;i<=n+1;++i) cin>>p[i];
for(int len=1;len<=n;++len){
for(int l=1;l+len-1<=n;++l){
int r=l+len-1;
if(len==1) dp[l][r]=0;
else{
dp[l][r]=1e9;
for(int k=l;k<r;++k){
int tmp=dp[l][k]+dp[k+1][r]+p[l]*p[k+1]*p[r+1];
if(tmp<dp[l][r]){
dp[l][r]=tmp;
s[l][r]=k;
}
}
}
}
}
cout<<dp[1][n]<<endl;
print(1,n);
return 0;
}