疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

最大矩阵连乘次数


 

    描述

  给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最大。

  输入

  输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n(n≤10),表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开。

  输出

  你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的矩阵最大连乘积次数。

  样例输入

  1

  3

  10 100 5 50

  样例输出

  75000

  #include

  #include

  #include

  using namespace std;

  int p[110],q[110],s[110];

  int max(int x,int y)

  {

  return x>y?x:y;

  }

  int dfs(int i,int j)

  {

  if(i==j)

  return 0;

  int mx=0;

  for(int k=i; k

  while(t--)

  {

  cin》n;

  for(int i=0;i<=n;i++)

  {

  cin》s[i];

  }

  for(int i=1;i<=n;i++)

  {

  p[i]=s[i-1];

  q[i]=s[i];

  }

  printf("%d ",dfs(1,n));

  }

  return 0;

  }