当前位置：首页 > news >正文

GXUOJ-算法-第二次作业

news 来源：原创 2025/5/14 5:59:36

1.矩阵连（链）乘

问题描述

GXUOJ | 矩阵连乘

代码解答

#include<bits/stdc++.h>
using namespace std;const int N=50;
int m[N][N];
int p[N];
int n;int main(){cin>>n;//m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。for(int i=0;i<=n;i++){cin>>p[i];m[i][i]=0;}for(int r=2;r<=n;r++){for(int i=1;i<=n-r+1;i++){int j=r+i-1;//初始化， m[i][j] 相当于 Ai，Ai+1···Aj 的最小乘积,	//m[i+1][j]是A【i+1]到A[j]的最小乘积 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//k=i+1/i  k<=j/k<j 四个结合都没有影响 for(int k=i+1;k<j;k++){int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j])m[i][j]=t;}}}cout<<m[1][n];
}

解题思路

i代表开始的下标，j代表结束的下标，r代表矩阵的长度。

m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。

当我们计算（Ai*···*Ak）和(Ak*···Aj)这两个子矩阵链乘结果相乘时，
就相当于计算两个矩阵相乘，其中第一个子矩阵链乘结果是
p[i-1]*p[k]一个的矩阵，第二个子矩阵链乘结果是p[k]*p[j]一个的矩阵。
根据矩阵乘法运算量的计算公式，这两个子矩阵链乘结果相乘所需的乘法次数就是
p[i - 1] * p[k] * p[j]。

2.最长公共子序列（LCS）

问题描述

GXUOJ | 最长公共子序列(LCS)

代码解答

#include<bits/stdc++.h>
using namespace std;int main(){string text1,text2;cin>>text1>>text2;int len1=text1.length();int len2=text2.length();//这两个都可以 //int len1=text1.size();//int len2=text2.size();int dp[1000][1000]={0};for(int i=0;i<len1;i++){for(int j=0;j<len2;j++){if(text1[i]==text2[j])//当前字符相等时，最长公共子序列长度在之前的基础上加 1dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);//这意味着取text1去掉当前字符与text2的最长公共子序列长度//和text2去掉当前字符与text1的最长公共子序列长度中的最大值。}}cout<<dp[len1][len2];return 0;
}

3.0-1背包问题

问题描述

GXUOJ | 0-1背包问题

代码解答

#include<bits/stdc++.h>
using namespace std;int n,m;
const int N=1005;
int w[N],v[N],dp[N];int main(){cin>>n>>m;for(int i=0;i<n;i++)cin>>v[i];for(int i=0;i<n;i++)cin>>w[i];for(int i=0;i<n;i++){for(int j=m;j>=w[i];j--){// 状态转移方程：选择当前物品或不选择当前物品中的较大价值dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m];
}

4.带权区间调度

问题描述

GXUOJ | 带权区间调度（Weighted Interval Scheduling）

代码解答

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct Task{int start,end,value;
}tasks[N];int dp[N];
bool compareTask(Task a,Task b){return a.end<b.end;
}
int find(int i){int l=0;int r=i-1;while(l<=r){int mid=(l+r)/2;// 如果中间位置任务的结束时间小于等于当前任务i的开始时间// 说明可能存在更靠后的不冲突任务，调整左边界if(tasks[mid].end<=tasks[i].start)l=mid+1;elser=mid-1;}return r;
}
int main(){int n;cin>>n;for(int i=0;i<n;i++)cin>>tasks[i].start>>tasks[i].end>>tasks[i].value;sort(tasks,tasks+n,compareTask);for(int i=0;i<n;i++){int x=find(i);dp[i+1]=max(dp[i],dp[x+1]+tasks[i].value);}cout<<dp[n];return 0;
}

GXUOJ-算法-第二次作业

1.矩阵连（链）乘问题描述 GXUOJ | 矩阵连乘代码解答 #include<bits/stdc.h> using namespace std;const int N50; int m[N][N]; int p[N]; int n;int main(){cin>>n;//m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小…...

编程日记 2025/5/14 5:59:36

BGP基础配置

使用直连接口IP地址来建立EBGP对等体关系 1、启动BGP协议 [r1]bgp 100 ----启动BGP协议，并且规定其AS号2、配置设备的RID数值，一般选择设备的loopback接口的IP地址 [r1-bgp]router-id 1.1.1.13、配置BGP对等体信息，包含了对等体的IP地址以及…...

编程日记 2025/5/10 9:50:18

瑞芯微全新芯片平台RK3506优势详解，高集成低功耗，为工业而生触觉智能测评

RK3506是瑞芯微Rockchip在2024年第四季度全新推出的Arm嵌入式芯片平台，三核Cortex-A7单核Cortex-M0多核异构设计，CPU频率达1.5Ghz, M0 MCU为200Mhz。而RK3506芯片平台下的工业级芯片型号RK3506J，具备-40-85℃的工业宽温性能、发热量小&#…...

编程日记 2025/5/8 16:38:37

Alice与Bob

Alice与Bob factordb.com 用上面链接可以直接分解得到101999和966233 按照要求让小的放前面大的放后面得到接着进行MD5的32位小写哈希 MD5在线加密/解密/破解—MD5在线 flag{d450209323a847c8d01c6be47c81811a}...

编程日记 2025/5/14 5:41:12

【玩转MacBook】Git安装

Git 官网也提到了MacBook 可以使用 Homebrew 安装 Git，所以在此使用 Homebrew 安装。 1、安装 Homebrew 执行安装脚本在 Terminal 中执行如下命令： /bin/bash -c "$(curl -fsSL https://gitee.com/ineo6/homebrew-install/raw/master/install.…...

编程日记 2025/5/14 5:06:12

【IC验证】verilog及systemverilog特殊特性的分析

verilog及systemverilog特殊特性的分析 1.概述2.赋值延迟（0）总结（1）情况一：initial中进行阻塞赋值和非阻塞赋值（不延迟）a代码b 电路图c 结果 （2）时钟a 代码b 电路图c 结果…...

编程日记 2025/5/14 5:45:59

Apollo中间件技术：从入门到精通

一、引言在Java开发的微服务架构中，配置管理是一个不可或缺的重要环节。随着服务数量的增加和部署环境的复杂化，传统的手动配置管理方式已难以满足需求。Apollo作为一款开源的分布式配置中心，凭借其强大的功能和灵活的架构，成为…...

编程日记 2025/5/13 10:02:45

汽车行业的MES系统方案（附案例资料合集）

针对汽车行业的MES系统方案，以下是一些关键点和实施案例： 核心功能： 实时监控：MES系统通过传感器和物联网技术实时监控生产线上的每一个环节，确保信息的及时传递。数据分析：系统对收集的数据进行深度分析&a…...

编程日记 2025/5/11 19:54:34

Python入门：7.Pythond的内置容器

引言 Python 提供了强大的内置容器（container）类型，用于存储和操作数据。容器是 Python 数据结构的核心部分，理解它们对于写出高效、可读的代码至关重要。在这篇博客中，我们将详细介绍 Python 的五种主要内置容器&…...

编程日记 2025/5/13 23:51:50

单片机与MQTT协议

MQTT 协议简述 MQTT（Message Queuing Telemetry Transport，消息队列遥测传输协议），是一种基于发布 / 订阅（publish/subscribe）模式的 “轻量级” 通讯协议，该协议构建于 TCP/IP 协议上&#xf…...

编程日记 2025/5/14 5:02:05

记录命令行操作树莓派Wifi的方式

打开WiFi rfkill unblock wlan 关闭WiFi rfkill block wlan 设置可连接的WiFi 方法一（bullseye及以前版本才可用，bookworm版本） sudo nano /etc/wpa_supplicant/wpa_supplicant.conf network{ssid"wifi_name"psk"wifi_pas…...

编程日记 2025/5/14 5:42:38

Docker 安装mysql ,redis,nacos

一、Mysql 一、Docker安装Mysql 1、启动Docker 启动：sudo systemctl start dockerservice docker start 停止：systemctl stop docker 重启：systemctl restart docker 2、查询mysql docker search mysql 3、安装mysql 3.1.默认拉取最新版…...

编程日记 2025/5/14 5:57:20

[C#] 复数乘法的跨平台SIMD硬件加速向量算法（不仅支持X86的Sse、Avx、Avx512，还支持Arm的AdvSimd）

文章目录一、简单算法二、向量算法2.1 算法思路2.1.1 复数乘法的数学定义2.1.2 复数的数据布局2.1.3 第1步：计算 (a*c) (-b*d)i2.1.4 第2步：计算 (a*d) (b*c)i2.1.5 第3步：计算结果合并 2.2 算法实现（UseVectors）2.…...

编程日记 2025/5/12 1:28:42

curl 放弃对 Hyper Rust HTTP 后端的支持

curl 放弃了对使用 Rust 编写 Hyper HTTP 后端的支持，因为用户和开发者对此功能的需求很少。 curl 创始人兼核心开发者 Daniel Stenberg 表示，尽管这项工作最初由 ISRG 赞助并且看起来很有希望，但 Hyper 支持多年来一直处于实验阶段&#xf…...

编程日记 2025/5/11 18:19:57

RK3506开发板：智能硬件领域的新选择，带来卓越性能与低功耗

在现代智能硬件开发中，选择一款性能稳定、功耗低的开发板是确保产品成功的关键。Rockchip最新推出的RK3506芯片，凭借其卓越的能效比、多功能扩展性和优秀的实时性能，已经成为智能家电、工业控制、手持终端等领域的热门选择。而基于RK3506的Ar…...

编程日记 2025/5/13 12:13:27

RBAC权限控制

1、Spring Security 是一个功能强大的Java安全框架，它提供了全面的安全认证和授权的支持。 2 SpringSecurity配置类（源码逐行解析） Spring Security的配置类是实现安全控制的核心部分开启Spring Security各种功能，以确保Web应…...

编程日记 2025/5/4 13:38:38

Linux高并发服务器开发第六天（rwx 对于目录和文件的区别 gcc编译器动态库静态库）

目录 1.rwx 对于目录和文件的区别 2.gcc 编译器 2.1编译过程 2.2gcc 的其他参数 3.动态库和静态库 3.1函数库 1.rwx 对于目录和文件的区别 r 文件的内容可以被查看。支持cat、more、head...vim ；目录的内容可以被查看。ls、tree …...

编程日记 2025/5/11 10:10:02

如何使用远程控制工具管理你的计算机系统

在现代工作环境中，远程控制技术越来越重要，尤其是对于系统管理员、技术支持人员以及需要远程工作的人来说。远程控制不仅仅是便捷，更是提高工作效率、快速解决问题的重要手段。今天，我们将讨论一些常见的远程控制工具，…...

编程日记 2025/5/12 3:54:45

在K8S中，CNI有什么作用？

在kubernetes中，Container Network Interface(CNI)起着至关重要的作用，主要解决了容器网络配置及通信的问题，确保了Pod间网络连通性及其外部世界的通信。CNI的具体作用包括但不限于以下几个方面。 1. 网络配置自动化： 当kuberne…...

编程日记 2025/5/12 18:00:34

C语言性能优化：从基础到高级的全面指南

引言 C 语言以其高效、灵活和功能强大而著称，被广泛应用于系统编程、嵌入式开发、游戏开发等领域。然而，要写出高性能的 C 语言代码，需要对 C 语言的特性和底层硬件有深入的了解。本文将详细介绍 C 语言性能优化的背后技术，并通过…...

编程日记 2025/4/24 22:06:37

JS中Symbol （符号）数据类型详解和应用场景

JavaScript中Symbol数据类型详解 Symbol是ES6引入的一种原始数据类型，表示唯一的标识符。它是通过Symbol()函数生成的，每次调用都会返回一个独一无二的值。Symbol值的主要用途是为对象的属性提供唯一标识，以避免属性名冲突。特点唯一性每…...

编程日记 2025/5/13 7:14:25

Go gin框架（详细版）

目录 0. 为什么会有Go 1. 环境搭建 2. 单-请求&&返回-样例 3. RESTful API 3.1 首先什么是RESTful API 3.2 Gin框架支持RESTful API的开发 4. 返回前端代码 go.main index.html 5. 添加静态文件 main.go?改动的地方 index.html?改动的地方 style.css?改…...

编程日记 2025/5/2 11:12:36

Linux系统 —— 进程控制系列 - 进程的等待：wait 与 waitpid

目录 1. 进程的等待 1.1 为什么需要等待 2. 进程等待的方法 1. wait 2. waitpid 3. 获取子进程status 4. 阻塞与非阻塞等待续接前文： Linux系统 —— 进程控制系列 - 进程的创建与终止 ：fork与exit-CSDN博客https://blog.csdn.net/hedhjd/artic…...

编程日记 2025/5/10 6:17:09

blender中合并的模型，在threejs中显示多个mesh；blender多材质烘培成一个材质

描述：在blender中合并的模型导出为glb，在threejs中导入仍显示多个mesh，并不是统一的整体，导致需要整体高亮或者使用DragControls等不能统一控制。原因：模型有多个材质，在blender中合并的时候，…...

编程日记 2025/5/14 1:58:09

探索多模态大语言模型（MLLMs）的推理能力 Multimodal Large Language Models (MLLMs) flyfish 原文：Exploring the Reasoning Abilities of Multimodal Large Language Models (MLLMs): A Comprehensive Survey on Emerging Trends in Mult…...

编程日记 2025/5/12 1:29:16

[Wireshark] 使用Wireshark抓包https数据包并显示为明文、配置SSLKEYLOGFILE变量（附下载链接）

wireshark 下载链接：https://pan.quark.cn/s/eab7f1e963be 提取码：rRAg 链接失效（可能会被官方和谐）可评论或私信我重发 chrome与firefox在访问https网站的时候会将密钥写入这个环境变量SSLKEYLOGFILE中，在wireshark…...

编程日记 2025/5/12 6:52:17

单片机实物成品-007 汽车防盗系统（代码+硬件+论文）

汽车尾气监测系统（温度震动传感器红外热释电GPS三个指示灯蜂鸣器正常模式防盗模式wifi传输控制送APP源码 ） 把该系统划分为两个不同设计主体，一方面为硬件控制主体，通过C语言来编码实现，以STM32开发板为核心控制器&a…...

编程日记 2025/5/12 17:46:55

redis开发与运维-redis0401-补充-redis流水线与Jedis执行流水线

文章目录【README】【1】redis流水线Pipeline【1.1】redis流水线概念【1.2】redis流水线性能测试【1.2.1】使用流水线与未使用流水线的性能对比【1.2.2】使用流水线与redis原生批量命令的性能对比【1.2.3】流水线缺点【1.3】Jedis客户端执行流水线【1.3.1】Jedis客户端执行流…...

编程日记 2025/5/11 17:46:17

windows系统下使用cd命令切换到D盘的方法

windows系统下使用cd命令切换到D盘的方法系统环境配置 win10系统原装C盘后期自己安装的硬盘D盘 python3.8安装在D盘中问题说明 winR打开终端，使用 cd d:命令，无法将当前目录切换到D盘解决方法方法一：使用下面这条命令 cd /d d:运…...

编程日记 2025/4/8 16:46:47

word参考文献第二行缩进对齐

刚添加完参考文献的格式是这样： ”段落“—>缩进修改、取消孤行控制就可以变成...

编程日记 2025/5/3 17:49:41

Springboot关于格式化记录

日期格式化返回前端日期需要格式化 <dependency><groupId>com.fasterxml.jackson.core</groupId><artifactId>jackson-databind</artifactId><version>2.9.2</version> </dependency>JsonFormat(pattern "yyyy-MM-dd…...

编程日记 2025/5/10 3:10:06

1.business english--build rapport

build rapport with someone 建立融洽关系 Salespeople often try to build rapport with customers to boost sales. user a variety of appropriate questions. answer the question according to your experience. Do you know how to make a good connection with others…...

编程日记 2025/5/14 0:06:56

1.矩阵连（链）乘

问题描述

代码解答

解题思路

2.最长公共子序列（LCS）

问题描述

代码解答

3.0-1背包问题

问题描述

代码解答

4.带权区间调度

问题描述

代码解答

相关文章：