import java.util.Scanner;
class Main {
// 定义矩阵类
static class Matrix {
int x, y; // x表示矩阵的行数,y表示矩阵的列数
}
static Matrix[] a; // 存储矩阵数组
static int[][] m; // 动态规划数组,用于存储最小乘法次数
// 计算矩阵链乘法的最小乘法次数
static int minmult(int n) {
// r 表示矩阵链的长度,从2开始遍历
for (int r = 2; r <= n; r++) {
int temp;
// i 表示链的起始位置
for (int i = 1; i <= n - r + 1; i++) {
int j = i + r - 1; // j 表示链的结束位置
// 初始值,计算将第i个矩阵乘到第j个矩阵的乘法次数
m[i][j] = m[i + 1][j] + a[i].x * a[i].y * a[j].y;
// k 表示分割点
for (int k = i + 1; k < j; k++) {
// 计算在第k个矩阵处分割后的乘法次数
temp = m[i][k] + m[k + 1][j] + a[i].x * a[k].y * a[j].y;
// 如果当前分割方式的乘法次数小于之前的值,则更新
if (m[i][j] > temp)
m[i][j] = temp;
}
}
}
return m[1][n]; // 返回最终结果,即从第1个矩阵到第n个矩阵的最小乘法次数
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt(); // 读取测试用例的数量
a = new Matrix[610]; // 初始化矩阵数组
m = new int[610][610]; // 初始化动态规划数组
for (int i = 0; i < t; i++) {
int n = scanner.nextInt(); // 读取矩阵数量
a = new Matrix[n + 1]; // 初始化当前用例的矩阵数组
for (int j = 1; j <= n; j++) {
a[j] = new Matrix();
a[j].x = scanner.nextInt(); // 读取矩阵的行数
a[j].y = scanner.nextInt(); // 读取矩阵的列数
}
int x = minmult(n); // 计算最小乘法次数
System.out.println(x); // 输出结果
}
scanner.close(); // 关闭扫描器
}
}
标签:连乘,Matrix,int,矩阵,static,数组,new
From: https://www.cnblogs.com/hanlinyuan/p/18288254