记录编号	264545	评测结果	AAAAAA
题目名称	矩阵连乘	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-05-28 18:13:39	内存使用	0.00 MiB

#include<stdio.h>
#include<string.h>
int f[20][20]={0},a[20]={0},p[20][20]={0};
int n,m,i,j,k,r;
int min(int x,int y){return x<y?x:y;}
void print(int x,int y)
{
	if(x==y) printf("A%d",x);
	else
	{
		printf("(");
		print(x,p[x][y]);
		print(p[x][y]+1,y);
		printf(")");
	}
}
int _521()
{
	freopen("t1.in","r",stdin);
	freopen("t1.out","w",stdout);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&n);
		for(i=0;i<=n;i++) scanf("%d",&a[i]);
		for(i=1;i<=n;i++)
		  f[i][i+1]=a[i]*a[i+1]*a[i-1],
		  p[i][i+1]=i;
		for(r=1;r<n;r++)
		{
			for(i=1;i<=n-r;i++)
			{
				j=r+i;f[i][j]=0x7fffffff;f[i][i]=0;
				for(k=i;k<j;k++)
				{
					if(f[i][j]>f[i][k]+f[k+1][j]+a[i-1]*a[k]*a[j])
					  f[i][j]=f[i][k]+f[k+1][j]+a[i-1]*a[k]*a[j],
					  p[i][j]=k;
				}
			}
		}
		printf("%d\n",f[1][n]);
		print(1,n);
		printf("\n");
	}
	return 0;
}
int _520=_521();
int main(){;}