记录编号	43785	评测结果	AAAAAA
题目名称	矩阵连乘	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-10-13 22:03:34	内存使用	3.15 MiB

// 2 errors found after submitted for 2 times
#include <iostream>
#include <cstdio>
using namespace std;

int a[20],f[20][20],rec[20][20];

int minint(int a,int b,int x,int y,int code)
{
    if(a<b)//attention: "<" can't be replaced by "<=" , because , for instance , when the f[][] value is equal , compared with (A1(A2A3)) , ((A1A2)A3) is considered in advance
        return(a);
	//else
    rec[x][y]=code;
    return(b);
}

void printit(int l,int x)// l means the No.l dividing line between A(l) and A(l+1)
{
    if (x==1)
    {
        cout<<'A'<<l;
        cout<<'A'<<l+1;
        return;
    }
    if (rec[l][x]==1)
    {
        cout<<'A'<<l;
        cout<<'(';
        printit(l+1,x-1);
        cout<<')';
        return;
    }
    if  (rec[l][x]==x)
    {
        cout<<'(';
        printit(l,x-1);
        cout<<')';
        cout<<'A'<<l+x;
        return;
    }
	//else
    cout<<'(';
    printit(l,/*3*/rec[l][x]-1/*3*/);
	//error 2 : /*3*/ used to be written as "x-rec[l][x]"
    cout<<')';
    cout<<'(';
    printit(l+rec[l][x],x-rec[l][x]);
    cout<<')';
}

int main(void)
{
    freopen("t1.in","r",stdin);
    freopen("t1.out","w",stdout);
    int times,i,j,k,m,n,l,r;
    cin>>m;
    for (times=1;times<=m;times++)
    {
        cin>>n;
        for (i=1;i<=n+1;i++)
            cin>>a[i];
        n--;//n means the number of dividing lines
        for (i=1;i<=n;i++)
        {
            f[i][1]=a[i]*a[i+1]*a[i+2];
            rec[i][1]=1;
        }
        for (i=1;i<n;i++)
        {
            f[i][2]=f[i+1][1]+a[i]*a[i+1]*a[i+3];//f[][] i+1 to i+1
            rec[i][2]=1;
            f[i][2]=minint(f[i][2],f[i][1]+a[i]*a[i+2]*a[i+3],i,2,2);//f[][] i to i
        }
        for (j=3;j<=n;j++)
            for (i=1;i+j-1<=n;i++)
            {
                l=i+1;
                r=i+j-2;
                /*1*/f[i][j]=f[i+1][j-1]+a[i]*a[i+1]*a[i+j+1];//f[][] i+1 to i+j-1
                rec[i][j]=1;
                for (k=l;k<=r;k++)
                    f[i][j]=minint(f[i][j],f[i][k-i]+f[k+1][i+j-k-1]+a[i]*a[k+1]*a[i+j+1],i,j,k-i+1);//f[][] i+1 to k-1 && k+1 to r
                /*2*/f[i][j]=minint(f[i][j],f[i][j-1]+a[i]*a[i+j]*a[i+j+1],i,j,j);//f[][] i to i+j-2
				//error 1 : the calculations in /*1*/ and /*2*/ has been reversed
            }
        cout<<f[1][n]<<endl;
        cout<<'(';
        printit(1,n);
        cout<<')';
        cout<<endl;
    }
    return(0);
}