#include<iostream>
#include<vector>

using namespace std;

int min[100][100];
int pos[100][100];
const int MAXINT = 100000000;
vector<int> rst;
//计算矩阵乘法的次数及断开位置
void matrix_mult(int n,vector<int> vec)
{
int temp;
for(int j = 1;j < n+1;j++)
for(int i = j;i > 0;i--)
{ if(i == j)
{min[i][j] = 0;}
else
{min[i][j] = MAXINT;
for(int k = i;k < j;k++)
{
temp = min[i][k] + min[k+1][j] + vec[i-1]*vec[k]*vec[j];
if(temp < min[i][j])
{
min[i][j] = temp;
pos[i][j] = k;
}
}
}
}
}
//计算x--y的断开顺序
void matrix_result(int x,int y)
{
if(y>x)
{
rst.push_back(pos[x][y]);
matrix_result(x,pos[x][y]);
matrix_result(pos[x][y]+1,y);
}
}
//显示所有结果
void display_result(int n)
{
for(int i=1;i<=n;i++)
{ for(int j=1;j<i;j++)
cout<<"POS["<<j<<"]["<<i<<"]="<<pos[j][i]<<" ";
cout<<endl;
}
for(i=1;i<=n;i++)
{ for(int j=1;j<i;j++)
cout<<"MIN["<<j<<"]["<<i<<"]="<<min[j][i]<<" ";
cout<<endl;
}
cout<<"\n矩阵连乘的最少数乘次数为: "<<min[1][n]<<endl;
cout<<"\n乘法分段次序依次为: START";
for(i=0;i<rst.size();i++)
cout<<"-->"<<rst[i];
cout<<"\n"<<endl;
}
void any_key_to_go_on()
{char choice;
cin.clear();
cout<<"\nPress any key to continue";
cout.clear();
cin >>noskipws>>choice;
}
//主函数
void main()
{
int n,elem;
vector<int> vec;
cout<<"请输入所有矩阵的阶(0结束): ";
while(cin>>elem)
if(elem != 0)
vec.push_back(elem);
else
break;
n = vec.size()-1;
cout<<'\n'<<"您输入的 "<<n<<" 个矩阵连乘如下:\n"<<endl;
for(int i=0;i<vec.size()-1;i++)
if(i!=vec.size()-2)
cout<<"M"<<i+1<<"("<<vec[i]<<"x"<<vec[i+1]<<") * ";
else
cout<<"M"<<i+1<<"("<<vec[i]<<"x"<<vec[i+1]<<")"<<endl;
matrix_mult(n,vec);
matrix_result(1,n);
display_result(n);
any_key_to_go_on();
any_key_to_go_on();
}