#include <iostream>#include <cstring>#include <cstdio>#define MAX 1000
using namespace std;
int m[MAX][MAX];int s[MAX][MAX];//fenge qingkuangint count = 0;
void MatrixChain(int p[],int n,int m[][MAX],int s[][MAX]){ for(int i = 1;i <= n;i++) m[i][i] = 0;
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[][MAX])//输出{ if(i == j ) cout<<"A"<<i; else{ cout<<"("; Traceback(i,s[i][j],s); cout<<" x "; Traceback(s[i][j]+1,j,s); cout<<")"; }}int main(){ // freopen("in.in","r",stdin); int n; int p[MAX];//维数 int count = 0; while(cin>>n && n){ count++; cout<<"Case "<<count<<": "; int temp,i; //输入维数 for( i = 0;i < n-1;i++) cin>>p[i]>>temp; cin>>p[i];i++; cin>>p[i];
MatrixChain(p,n,m,s);//DP求解
Traceback(1,n,s);
cout<<endl; } return 0;}