最大矩阵连乘次数

描述

给定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行，即每组测试数据的输出占一行，它是计算出的矩阵最大连乘积次数。

样例输入

样例输出

#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
     
      >t; 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\n",dfs(1,n)); } return 0; }