#include<iostream.h>
void chain(int n,int p[],int **m,int **s)
//p[n-1]*p[n]為An的下標(biāo)
//s[i][j],m[i][j]分別為Ai到Aj最小運算分法的點和值
//n為總運算的元素個數(shù)
{
	for(int i=1;i<=n;i++) m[i][i]=0;//只有1個元素則不做任何操作
	for(int num=2;num<=n;num++)//num表示元素個數(shù)
	{
		for(int i=1;i<=n-num+1;i++)//按所含元素個數(shù)從小往大算
		{
			int j=i+num-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 min=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(min<m[i][j])//比較，如有更小分法則記錄
				{
					m[i][j]=min;
					s[i][j]=k;
				}
			}
		}
	}
}
void kuohao(int i,int j,int khl[],int khr[],int **s)
{
	if(j-i>=2)
	{
		if(s[i][j]==i)//形如Ai(┈Aj)的情況
		{
			khl[i]++;
			khr[j]++;
		}
		else if(s[i][j]==j-1)//形如(Ai┈)的Aj情況
		{
			khl[i-1]++;
			khr[j-1]++;
		}
		else//形如(Ai┈Ak)(┈Aj)的情況
		{
			khl[i-1]++;
			khl[s[i][j]]++;
			khr[s[i][j]]++;
			khr[j]++;
		}
		kuohao(i,s[i][j],khl,khr,s);
		kuohao(s[i][j]+1,j,khl,khr,s);
	}
}
void main()
{
	int n;
	cout<<"輸入數(shù)據(jù)的個數(shù):  ";
	cin>>n;
	int *p=new int[n+1];//p[n-1]*p[n]為An的下標(biāo)
	int *khl=new int[n+1];//khl[i]記錄Ai右邊的左括號數(shù)目
	int *khr=new int[n+1];//khr[i]記錄Ai右邊的右括號數(shù)目
	cout<<endl<<"輸入p[0]至p["<<n<<"]的值(p[n-1]*p[n]為An的下標(biāo)):  "<<endl;
	for(int i=0;i<=n;i++)
	{
		cin>>p[i];
		khl[i]=0;
		khr[i]=0;
	}
	khl[0]=1;
	khr[n]=1;
	int **m=new int*[n+1];
	int **s=new int*[n+1];//s[i][j],m[i][j]分別為Ai到Aj最小運算分法的點和值
	for(int j=1;j<=n;j++)
	{
		m[j]=new int[n+1];
		s[j]=new int[n+1];
	}
	chain(n,p,m,s);
	kuohao(1,n,khl,khr,s);
	cout<<endl<<"最優(yōu)計算次序"<<endl;
	for(int k=0;k<=n;k++)
	{		
		if(k>0)
		{
			cout<<"A"<<k;
		}
		for(int num=khr[k];num>0;num--)
		{
			cout<<")";
		}
		for(num=khl[k];num>0;num--)
		{
			cout<<"(";
		}
	}
	cout<<endl;
}