1900_算法设计例题：矩阵连乘（DP）

给定n个矩阵{ A₁，A₂，…，A_n }，保证A_i与A_i+1是可乘的，i = 1，2，…，n-1。考察这n个矩阵的连乘积A₁A₂…A_n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。现要求设计一个高效的算法，对给定的n个矩阵确定一个计算次序使得总的乘法次数最少，并输出该最优值。

输入的第一行是单独一个整数T，表示案例的数目。每个案例的第一行是单独一个n ( 1 ≤ n ≤ 600 )，表示矩阵的个数。接下来第n行，依序分别对应第i个矩阵，每行包括两个整数x_i，y_i (1 ≤ i ≤ n，1 ≤ x_i , y_i ≤ 100 )，表示该矩阵的行数和列数。保证n个矩阵依序是可乘的。

每个案例输出一个整数，表示最少需要的乘法次数。 运算过程及结果不会超出int范围。

1
4
50 10
10 40
40 30
30 5

10500