juzhenliancheng.rar_multiplicative

#include<iostream> #define x 21 using namespace std; int p[x]; int m[x][x]; int s[x][x]; int flag; int n; void MatricChain(int p[],int n,int m[x][x],int s[x][x]){ for(int i=1;i<=n;i++) for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++){ int j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; 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; } } } } void Traceback(int i,int j,int s[x][x]){ if(i==j) { cout<<"A"<<i<<""; return; } else if (i+1==j) { if(n==2) cout<<"A"<<i<<"A"<<j; else cout<<"(A"<<i<<"A"<<j<<")"; } else{ if(i!=1||j!=n) cout<<"("; if(i+1==s[i][j]) cout<<"(A"<<i<<"A"<<s[i][j]<<")"; else Traceback(i,s[i][j],s); cout<<""; if(s[i][j]+1+1==j) cout<<"(A"<<s[i][j]+1<<"A"<<j<<")"; else Traceback(s[i][j]+1,j,s); if(i!=1||j!=n) cout<<")"; } } int main(){ int k=0; while(cin>>n){ int i,j; for(i=0;i<=n;i++){ p[i]=0; for(j=0;j<=n;j++){ m[i][j]=0; s[i][j]=0; } } for(i=0;i<=n;i++) cin>>p[i]; MatricChain(p,n,m,s); cout<<"Case"<<" "<<++k<<endl; cout << m[1][n] << " "; Traceback(1,n,s); } return 0; }