首页 > 其他分享 >矩阵连乘

矩阵连乘

时间:2024-07-07 10:30:46浏览次数:14  
标签:连乘 Matrix int 矩阵 static 数组 new

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

相关文章

  • L1-048 矩阵A乘以B
    给定两个矩阵A和B,要求你计算它们的乘积矩阵AB。需要注意的是,只有规模匹配的矩阵才可以相乘。即若A有Ra​行、Ca​列,B有Rb​行、Cb​列,则只有Ca​与Rb​相等时,两个矩阵才能相乘。输入格式:输入先后给出两个矩阵A和B。对于每个矩阵,首先在一行中给出其行数R和列数C,随后R行,每行给......
  • 矩阵键盘与密码锁
    目录1.矩阵键盘介绍​编辑 2.扫描的概念3.代码演示(读取矩阵键盘键码)4.矩阵键盘密码锁1.矩阵键盘介绍为了减少I/O口的占用,通常将按键排列成矩阵形式,采用逐行或逐列的“扫描”,就可以读出任何位置按键的状态 2.扫描的概念1)数码管扫描(输出扫描)原理:显示第1位→显示......
  • 【C语言习题】33.杨氏矩阵
    文章目录作业标题作业内容2.解题思路3.具体代码作业标题杨氏矩阵作业内容有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。要求:时间复杂度小于O(N);2.解题思路我们仔细分析,不难发现,对于杨氏......
  • 流量时代——企业如何运营短视频矩阵
    在数字化时代,短视频平台的兴起为同城商家提供了全新的营销机遇。要做好短视频矩阵流量,同城商家可以采取以下策略:扩大品牌曝光:通过注册多个抖音账号,形成矩阵效应,以提升品牌知名度和曝光率;精准定位目标用户:分析目标用户的兴趣爱好和行为特征,制定符合他们喜好的视频策略,精准......
  • LeetCode刷题之搜索二维矩阵
    20247/5一如既往的晴天,分享几张拍的照片嘿嘿,好几天没做题了,在徘徊、踌躇、踱步。蝉鸣的有些聒噪了,栀子花花苞也都掉落啦,今天给他剪了枝,接回一楼来了。ok,做题啦!图1、宿舍阳台摄,每天都是如此美景图2、吃饭路上桥上摄图3、桥的另一边摄okok,做题啦!1、题目描述2、算......
  • .NET 矩阵6月红队工具和资源集合
    01外网入口打点1.1Sharp4WbemScripting1.2ASP4Eval1.3Sharp4Web.config1.4Sharp4AddScript02安全防御绕过2.1Sharp4DefenderStop03搭建代理隧道3.1Sharp4suo504混淆加密防护4.1Obfuscar混淆器4.2Sharp4BatchGuard05安全技术文档5.1......
  • Day2 |977.有序数组的平方& 209.长度最小的子数组&59.螺旋矩阵II
    977.有序数组的平方这题太简单了,中间的排序我用的选择排序贴代码了publicint[]sortedSquares(int[]nums){for(inti=0;i<nums.length;i++){nums[i]=nums[i]*nums[i];}for(inti=0;i<nums.length;i++){......
  • 代码随想录刷题day 2 | 977.有序数组的平方、 209.长度最小的子数组、 59.螺旋矩阵II
    977.有序数组的平方classSolution{publicint[]sortedSquares(int[]nums){int[]ans=newint[nums.length];intleft=0,right=nums.length-1;for(inti=nums.length-1;i>=0;i--){if(nums[right]*nums[righ......
  • 如何通俗易懂的理解雅可比矩阵
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言一、雅可比矩阵是什么?二、更具体的解释:1.多变量函数2.偏导数3.雅可比矩阵为什么雅可比矩阵重要?总结前言雅可比矩阵(Jacobianmatrix)是一个重要的数学概念,尤其在多变量函数微分学中有着广......
  • 《安富莱嵌入式周报》第339期:单片机运行苹果早期Mac系统模拟器,2GHz示波器有源探头,下一
    周报汇总地址:http://www.armbbs.cn/forum.php?mod=forumdisplay&fid=12&filter=typeid&typeid=104 视频版https://www.bilibili.com/video/BV1Kf421Q7Lh目录1、开源2GHz的示波器有源探头2、模拟矩阵开关面包板Jumperless推出下一代JumperlessV53、软件相关(1)Swifton......