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

GXUOJ-算法-第二次作业（矩阵连乘、最长公共子序列、0-1背包问题、带权区间调度）

news 来源：原创 2025/7/20 16:56:18

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[x + 1]代表的是在任务i之前且与任务i兼容（不冲突）的任务中，//能够获得的最大价值。dp[i+1]=max(dp[i],dp[x+1]+tasks[i].value);}cout<<dp[n];return 0;
}

GXUOJ-算法-第二次作业（矩阵连乘、最长公共子序列、0-1背包问题、带权区间调度）

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/7/20 16:56:18

生态碳汇涡度相关监测与通量数据分析实践技术应用

1.以涡度通量塔的高频观测数据为例，基于MATLAB开展上机操作： 2.涡度通量观测基本概况：观测技术方法、数据获取与预处理等 3.涡度通量数据质量控制：通量数据异常值识别与剔除等 4.涡度通量数据缺失插补：结合气象数据…...

编程日记 2025/7/15 1:17:08

使用OpenAI、LangChain、MongoDB构建一个AI agent

LangChain真是好起来了。24年中的时候用LangChain V2差点把我气死，现在V3用起来开始真香了~ 像 ChatGPT、Gemini 和 Claude 这样的大模型已成为企业必不可少的工具。如今，几乎每家公司都希望根据自己的需求或客户群体，开发一款定制化的AI Age…...

编程日记 2025/7/18 9:25:52

如何在 Ubuntu 22.04 上安装并开始使用 RabbitMQ

简介消息代理是中间应用程序，在不同服务之间提供可靠和稳定的通信方面发挥着关键作用。它们可以将传入的请求存储在队列中，并逐个提供给接收服务。通过以这种方式解耦服务，你可以使其更具可扩展性和性能。 RabbitMQ 是一种流行的开源消息代…...

编程日记 2025/7/13 5:49:19

【ETCD】【实操篇（十九）】ETCD基准测试实战

目录 1. 设定性能基准要求2. 使用基准测试工具基准测试命令 3. 测试不同的负载和场景4. 监控集群性能5. 评估硬件和网络的影响6. 对比性能基准7. 负载均衡和容错能力测试8. 优化与调优9. 测试在高负载下的表现总结 1. 设定性能基准要求首先，明确集群性能的目标&am…...

编程日记 2025/7/18 14:36:08

HTML——29. 音频引入二

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>音频引入</title></head><body><!--audio:在网页中引入音频IE8以及之前版本不支持属性名和属性值一样，可以只写属性名src属性:指定音频文件…...

编程日记 2025/7/16 5:21:15

【SQLi_Labs】Basic Challenges

什么是人生？人生就是永不休止的奋斗！ Less-1 尝试添加’注入，发现报错这里我们就可以直接发现报错的地方，直接将后面注释，然后使用 1’ order by 3%23 //得到列数为3 //这里用-1是为了查询一个不存在的id,好让第一…...

编程日记 2025/7/19 21:23:47

InnoDB存储引擎对MVCC的实现

多版本并发控制 (Multi-Version Concurrency Control) MVCC（Multi-Version Concurrency Control），即多版本并发控制，是一种并发控制方法，主要用于数据库管理系统中实现对数据库的并发访问。以下是MVCC的详细解释&#…...

编程日记 2025/7/16 16:05:56

3D线上艺术展：艺术与技术的完美融合

随着数字技术的飞速发展，未来的艺术展览正逐步迈向线上线下融合的新阶段。其中，3D线上展览以其独特的魅力，成为线下展览的延伸与拓展，为艺术爱好者们开辟了全新的观赏途径。对于艺术家和策展人而言，3D线上展览不仅打…...

编程日记 2025/7/15 14:43:23

EasyExcel（读取操作和填充操作）

文章目录 1.准备Read.xlsx（具有两个sheet）2.读取第一个sheet中的数据1.模板2.方法3.结果 3.读取所有sheet中的数据1.模板2.方法3.结果 EasyExcel填充1.简单填充1.准备 Fill01.xlsx2.无模版3.方法4.结果 2.列表填充1.准备 Fill02.xlsx2.模板3.方法4.结果 …...

编程日记 2025/7/18 7:22:04

【CSS in Depth 2 精译_095】16.3：深入理解 CSS 动画（animation）的性能

当前内容所在位置（可进入专栏查看其他译好的章节内容） 第五部分添加动效 ✔️【第 16 章变换】 ✔️ 16.1 旋转、平移、缩放与倾斜 16.1.1 变换原点的更改16.1.2 多重变换的设置16.1.3 单个变换属性的设置 16.2 变换在动效中的应用 16.2.1 放大图标&am…...

编程日记 2025/7/19 14:57:28

目前最流行的 Rust Web 框架有哪些？

目前最流行的 Rust Web 框架有哪些？ 1. Actix Web：高性能之王，老牌框架特点：高性能：基于 Actor 模型，是目前 Rust 生态中最成熟、性能最强的 Web 框架之一。功能强大：支持 HTTP/1.x、HTTP/2、WebSocket 等，内置中间件和多种插件。社区支持广泛：拥有大量使用者，资料…...

编程日记 2025/7/19 20:04:20

连锁餐饮行业数据可视化分析方案

引言随着连锁餐饮行业的迅速发展，市场竞争日益激烈。企业需要更加精准地把握运营状况、消费者需求和市场趋势，以制定科学合理的决策，提升竞争力和盈利能力。可视化数据分析可以帮助连锁餐饮企业整合多源数据，通过直观、动态的可…...

编程日记 2025/7/19 23:24:34

如何通过采购管理系统提升供应链协同效率？

供应链是企业运营的命脉，任何环节的延迟或失误都会对企业造成严重影响。在采购环节中，如何保证与供应商的协同效率，避免因信息不对称而导致的决策失误，是企业面临的一大挑战。采购管理系统作为数字化供应链管理的重要工具&#xf…...

编程日记 2025/7/15 1:31:55

1、Jmeter、jdk下载与安装

1、访问官网，点击下载Jmeter http://jmeter.apache.org/ 2、在等待期间，下载对应的Java https://www.oracle.com/cn/java/technologies/downloads/#jdk23-windows 3、全部下载好，先安装JDK ![在这里插入图片描述](https://i-blog.csdnimg…...

编程日记 2025/7/15 13:57:24

package org.app package daoimport org.app.models.BookModelimport scala.collection.mutable.ListBuffer//图书，数据操作层 class BookDAO {//加载图书，从文件中读入def loadBooks(): ListBuffer[BookModel] {val books new ListBuffer[BookModel](…...

编程日记 2025/7/18 4:48:53

Java 类加载机制

什么是类类是现实世界的实体在计算中的映射、它将数据以及对这些数据的操作封装在一起。类加载的定义类加载是 JVM 运行时的一个动作、支持将 class 动态加载到 JVM 中类加载是一种懒加载模式、按需加载。类加载到五个过程加载验证准备解释初始化提一点&#xff0…...

编程日记 2025/7/19 11:24:46

Lombok是银弹？还是陷阱？

Lombok 是一个 Java 库，它通过注解简化和减少了 Java 中的样板代码（boilerplate code），例如 getter/setter 方法、构造函数、equals 和 hashCode 方法等。对于是否将 Lombok 视为“银弹”或“陷阱”，这实际上取决于你…...

编程日记 2025/7/19 1:36:39

大数据技术-Hadoop（四）Yarn的介绍与使用

目录一、Yarn 基本结构 1、Yarn基本结构 2、Yarn的工作机制二、Yarn常用的命令三、调度器 1、Capacity Scheduler（容量调度器） 1.1、特点 1.2、配置 1.2.1、yarn-site.xml 1.2.2、capacity-scheduler.xml 1.3、重启yarn、刷新队列测试向hi…...

编程日记 2025/7/16 7:34:07

CentOS修改docker镜像存储位置并进行数据迁移

在 CentOS 上修改 Docker 镜像存储位置并进行数据迁移是一个常见的需求。以下是一个详细的步骤指南，帮助你完成这个任务。 1. 停止 Docker 服务首先，确保 Docker 服务已经停止，以避免在迁移过程中出现数据损坏。 sudo systemctl stop doc…...

编程日记 2025/7/15 13:41:08

xterm + vue3 + websocket 终端界面

xterm.js 下载插件 // xterm npm install --save xterm// xterm-addon-fit 使终端适应包含元素 npm install --save xterm-addon-fit// xterm-addon-attach 通过websocket附加到运行中的服务器进程 npm install --save xterm-addon-attach <template><div :…...

编程日记 2025/7/15 17:45:46

解锁 CSS：网页美化与布局的艺术

目录一、CSS 是什么二、CSS 的作用三、CSS 的应用方式（引用方式） 四、选择器：如何挑选要 “打扮” 的元素五、CSS 属性：丰富多样的 “服装款式” 字体属性： 文本属性：只能控制文字的相关样式。 …...

编程日记 2025/7/14 16:11:18

AWS K8s 部署架构

Amazon Web Services（AWS）提供了一种简化的Kubernetes（K8s）部署架构，使得在云环境中管理和扩展容器化应用变得更加容易。这个架构的核心是AWS EKS（Elastic Kubernetes Service），它是…...

编程日记 2025/7/16 14:46:23

【鸿蒙NEXT】鸿蒙里面类似iOS的Keychain——关键资产(@ohos.security.asset)实现设备唯一标识

前言在iOS开发中Keychain 是一个非常安全的存储系统，用于保存敏感信息，如密码、证书、密钥等。与 NSUserDefaults 或文件系统不同，Keychain 提供了更高的安全性，因为它对数据进行了加密，并且只有经过授权的应用程序才…...

编程日记 2025/7/19 10:03:02

电子电器架构 --- HUD的工作原理

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师：所谓鸡汤，要么蛊惑你认命，要么怂恿你拼命，但都是回避问题的根源，以现象替代逻辑，以情绪代替思考，把消极接受现实的懦弱，伪装成乐观面对不幸的…...

编程日记 2025/7/18 20:53:03

C# 窗体应用程序嵌套web网页，基于谷歌浏览器内核（含源码）

有一个winform项目，需要借助一个web项目来显示，并且对web做一些操作,web页目是需要用谷歌内核，基于谷歌 Chromium项目的开源Web Browser控件来开发写了一个demo。安装步骤第一步：右键项目，点击管理NuGet程序包 , 输…...

编程日记 2025/7/14 21:55:35

FFmpeg 中 examples 使用教程

FFmpeg 中 examples FFmpeg 的 examples 目录包含了一系列示例程序，旨在展示如何使用 FFmpeg 的不同库和 API。这些示例涵盖了多种功能，包括音视频编解码、格式转换、过滤、网络传输等。以下是一些常见的示例程序及其功能介绍：音频和视频解码：示例程序展示了如何打开音视…...

编程日记 2025/7/19 20:31:45

自动化办公-合并多个excel

在日常的办公自动化工作中，尤其是处理大量数据时，合并多个 Excel 表格是一个常见且繁琐的任务。幸运的是，借助 Python 语言中的强大库，我们可以轻松地自动化这个过程。本文将带你了解如何使用 Python 来合并多个 Excel 表格&#…...

编程日记 2025/7/19 16:20:16

Docker搭建MySQL

Docker搭建MySQL 准备工作先准备配置目录和持久化目录，举个栗子：mkdir -p /opt/module/mysql/{conf,data,log}准备配置文件*.cnf,放到/opt/module/mysql/conf目录下。当然不准备也没事，容器中有个默认配置：/etc/mysql/conf.d/m…...

编程日记 2025/7/19 8:39:42

亚马逊国际站商品爬虫：Python实战指南

在数字化时代，数据的价值不言而喻。对于电商领域而言，获取竞争对手的商品信息、价格、评价等数据，对于市场分析和策略制定至关重要。本文将带你了解如何使用Python编写爬虫，以亚马逊国际站为例，按照关键字搜索并获取商…...

编程日记 2025/7/20 14:35:00

pwntools用法

pwntools 是一个Python库， 用于编写二进制漏洞利用（exploitation）脚本功能： 远程连接和本地连接： 支持通过TCP/UDP连接远程服务或与本地进程进行交互。Shellcode和ROP链构造： 提供了便捷的工具来生成和利…...

编程日记 2025/7/15 22:53:33

企业云盘怎么选？2024年免费版9款整理

文章介绍了以下9大企业云盘：1.亿方云；2.Worktile；3.百度网盘；4.腾讯云盘；5.阿里云盘；6.金山云盘；7.Dropbox；8.Box。在企业日常管理中，文件存储和共享一直是个不小的难题…...

编程日记 2025/7/19 9:46:31

Linux之ARM(MX6U)裸机篇----5.仿stm32的LED驱动实验

一，启动文件 .global _start .global _bss_start /* 类似宏定义把__bss_start定义为_bss_start */ _bss_start:.word __bss_start.global _bss_end _bss_end:.word __bss_end_start:#设置处理器进入SVC模式mrs r0, cpsr /* 读取cpsr到r0 */bic r0, r0, …...

编程日记 2025/7/17 5:46:08

Qt从入门到入土（七）-实现炫酷的登录注册界面（下）

前言 Qt从入门到入土（六）-实现炫酷的登录注册界面（上）主要讲了如何使用QSS样式表进行登录注册的界面设计，本篇文章将介绍如何对登录注册界面进行整体控件的布局，界面的切换以及实现登录、记住密码等功能。…...

编程日记 2025/7/15 13:18:32

如何进行年度工作回顾？

发生了什么事？ 什么事情进展顺利 ？ 什么事情进展不顺利？ 如何适应未来？ 年度回顾的定义：这是一种战略工具，能帮助人们清晰看到过去一年对业务、职业或个人生活的影响，可用于明确关键事件、找出问…...

编程日记 2025/7/19 4:24:26

spring默认线程池SimpleAsyncTaskExecutor特点为什么要尽量避免使用

在 Spring Boot 中，默认的线程池配置由 TaskExecutionAutoConfiguration 类提供，使用的是 SimpleAsyncTaskExecutor。 SimpleAsyncTaskExecutor特点每次调用创建新线程： SimpleAsyncTaskExecutor 每次执行任务时都会创建一个新线程&#xf…...

编程日记 2025/7/15 14:09:31

每天40分玩转Django：Django表单集

Django表单集一、知识要点概览表类别知识点掌握程度要求基础概念FormSet、ModelFormSet深入理解内联表单集InlineFormSet、BaseInlineFormSet熟练应用表单集验证clean方法、验证规则熟练应用自定义配置extra、max_num、can_delete理解应用动态管理JavaScript动态添加/删除表…...

编程日记 2025/7/18 14:25:24

构建混合技术栈的统一监控与日志平台

文章目录摘要引言构建统一监控与日志平台的核心思路痛点分析解决方案平台架构设计架构概览环境准备Java 服务的 Prometheus 指标导出Prometheus 指标采集模块Node.js 日志收集模块3. Logstash 配置4. Grafana 与 Kibana 配置 QA 环节总结未来展望参考资料摘要在多技术栈开…...

编程日记 2025/7/18 4:51:06

KOI技术-事件驱动编程（Sping后端）

1 “你日渐平庸，甘于平庸，将继续平庸。”——《以自己喜欢的方式过一生》 2. “总是有人要赢的，那为什么不能是我呢?”——科比布莱恩特 3. “你那么憎恨那些人，和他们斗了那么久，最终却要变得和他们一样，…...

编程日记 2025/7/17 22:43:11

ubuntu 20.04 国内源安装docker

先更新软件包，安装备要apt软件 # 更新软件包索引 sudo apt-get update# 安装需要的软件包以使apt能够通过HTTPS使用仓库 sudo apt-get install ca-certificates curl gnupg lsb-release使用阿里云源 # 添加阿里云官方GPG密钥 curl -fsSL http://mirrors.aliyun.co…...

编程日记 2025/7/19 18:30:52

微信小程序 app.json 配置文件解析与应用

目录一、什么是 app.json？ 二、app.json 文件的基本结构三、详细解析 app.json 配置项 1. pages：小程序页面路径配置 2. window：窗口样式配置 3. tabBar：底部标签栏配置 4. networkTimeout：网络请求超时配置 …...

编程日记 2025/7/16 4:30:31

C高级：思维导图Day2

目录总览1 总览2 总览1 压缩与解压缩打包与解包软连接与硬链接 ubuntu下关机与重启指令总览2 结束...

编程日记 2025/7/19 4:35:39

蓝桥杯（Java）（ing）

Java前置知识输入流： （在Java面向对象编程-CSDN博客里面有提过相关知识------IO流） // 快读快写 static BufferedReader in new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out new BufferedWriter(new…...

编程日记 2025/7/19 15:39:24

[Pro Git#2] 分支管理 | branch fix_bug , feature | 处理合并冲突

目录一、Issue模板文件二、Pull Requests模板文件分支管理 1. 理解分支 2. 创建与管理分支 1. 切换分支与提交历史 2. 合并分支 3. 删除分支 4. 解决合并冲突 6. 查看分支合并情况快速创建并切换分支分支管理策略分支合并模式分支管理原则日常开发环境 …...

编程日记 2025/7/16 15:57:03

Java——集合框架

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录 1 集合框架概述1.1 内存层面需要针对多个数据进行存储。此时，可以考虑的容器有：1.2 数组存储多个数据方面的特点和弊端1.3 Java集合框架体系…...

编程日记 2025/7/18 15:21:14

Mac 环境 VVenC 编译与编码命令行工具使用教程

VVenC VVenC 是一个开源的高效视频编码器，专门用于支持 H.266/VVC (Versatile Video Coding) 标准的编码。H.266/VVC 是继 HEVC (H.265) 之后的新一代视频编码标准，主要目的是提供比 HEVC 更高的压缩效率，同时保持或提高视频质量。H.266/VVC…...

编程日记 2025/7/15 22:13:09

WebRTC：实现浏览器与移动应用的实时通信

1.技术简介 （Web Real-Time）是一种开放式实时通信技术，旨在使浏览器和移动应用程序通过简单的API即可实现实时音频、视频和数据传输，而无需安装插件或额外软件。它支持网络应用中的点对点通信，例如视频聊天、语音通话…...

编程日记 2025/7/19 23:49:38

curl+openssl 踩坑笔记

curl编译：点击跳转踩坑一 * SSL certificate problem: unable to get local issuer certificate * closing connection #0 curl: (60) SSL certificate problem: unable to get local issuer certificate More details here: https://curl.se/docs/sslcerts.html …...

编程日记 2025/7/14 23:29:51