import ;
public class MatrixMulBestOrder {
private static int[][] sign;
private static int d[][]=new int[102][2];//d[i][0]为第i个空隙中左括号的数量，d[i][1]为第i个空隙中右括号的数量
private static final int N=10;
public static void main(String[] args) {
/*
模拟10个矩阵，行列数存储在数组c中
对于1<=i<=N,令c[i]是矩阵A(i)的列数。于是A(i)有c[i-1]行。
*/
int row,col;
int[] c=new int[N+1];//只有10个矩阵，但是创建容量为11的数组，c[0]是第一个矩阵的行数
Random random=new Random();
row = (60)+1;
c[0]=row;//只需给第1个矩阵的行赋值，因为其他矩阵的行数即为前一个矩阵的列数
/*
c[1]才是第1个矩阵的列数,c[10]是第10个矩阵的列数
*/
for (int i=1;i<=N;i++) {
col=(60)+1;
c[i]=col;
}
for(int i=1;i<=N;i++){
("---第"+i+"个矩阵的行、列数为"+c[i-1]+","+c[i]+"---");
if (i%5==0) ();
}
//输出c数组
/*("数组c:");
for (int i=0;i<=N;i++)
(c[i]+" ");
();*/
long[][] m=new long[N+1][N+1];
int[][] lastChange=new int[N+1][N+1];
optMatrix(c,m,lastChange);
for (int j=1;j<=N+1;j++){
d[j][0]=0;
d[j][1]=0;
}
numBrackets(1,N);
for (int j=1;j<=N+1;j++){
for (int t=0;t<d[j][1];t++) //由于不可能出现先左括号后右括号相邻的情况，因此右括号先输出
(")");
if (j>1&&j<N+1)
("*");
for (int t=0;t<d[j][0];t++)
("(");
if(j<N+1)
("A"+j);
}
}
public static void optMatrix(int[] c,long[][] m,int[][] lastChange){
int n=-1;//c有n
for (int left=1;left<=n;left++) {
/*
m[left][right]是进行矩阵乘法A(left)A(left+1)...A(right-1)A(right)所需要的乘法次数。
当只有1个矩阵时，乘法次数为0,所以m[left][left]=0;
*/
m[left][left] = 0;
}
for(int k = 1; k < n; k++)
for(int left = 1; left <= n-k; left++){
int right = left + k;
m[ left ][ right ] = Long.MAX_VALUE;
for( int i = left; i < right; i++){
/*
这三项分别代表计算A(left)...A(i),A(i+1)...A(right)以及它们的乘积所需的乘法次数
*/
long thisCost = m[ left ][ i ] + m[ i + 1][ right ]
+ c[ left - 1] * c[ i ] * c[ right ];
if (thisCost < m[ left ][ right ]){ //Update min
m[ left ][ right ] = thisCost;
lastChange[ left ][ right ] = i;// i为m[left][right]最小时的分割两段矩阵的位置
}
}
}
sign=lastChange;
//输出m数组
/*for (int x=0;x<=N;x++)
for (int y=0;y<=N;y++) {
(m[x][y]+" ");
if (y==N) ();
}*/
//输出lastChange数组
for (int x=0;x<=N;x++)
for (int y=0;y<=N;y++) {
(lastChange[x][y]+" ");
if (y==N) ();
}
/*
"第"+left+"个矩阵到第"+right+"个矩阵所需乘法次数为:"+m[left][right]
*/
int huanhang=1;
for(int left=1;left<N;left++){
for(int right=left+1;right<=N;right++){
(left+"->"+right+": "+m[left][right]+" ");
if (huanhang%5==0) ();
huanhang++;
}
}
}
/*
为每个间隔i确定左、右括号数量
(括号 和 *号)
*/
private static void numBrackets(int left,int right){
if(right-left<=1) return;
int i=sign[left][right];
if (i>left){
d[left][0]++;
d[i+1][1]++;
}
if (right>i+1){
d[i+1][0]++;
d[right+1][1]++;
}
numBrackets(left, sign[left][right]);
numBrackets(sign[left][right] + 1, right);
}
}