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

GXUOJ-算法-第二次作业

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.矩阵连&#xff08;链&#xff09;乘 问题描述 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 个矩阵这一段矩阵链相乘的最小…...

Gavin Wood 的 Polkadot 2024 年度回顾:技术突破与未来的无限可能

原文&#xff1a;https://medium.com/polkadot-network/polkadot-roundup-mmxxiv-8d3e880dd637 作者&#xff1a;Gavin Wood 编译&#xff1a;OneBlock &#x1f384; 各位波卡生态的 Buidler 们&#xff0c;圣诞快乐&#xff01;在这个充满节日气氛的时刻&#xff0c;很高兴与…...

AduSkin、WPF-UI、Prism:WPF 框架全解析与应用指南

摘要: 本文深入探讨了 AduSkin、WPF-UI、Prism 这三个在 WPF 开发领域极具影响力的框架。详细阐述了每个框架的特点、核心功能、安装与配置过程,并通过丰富的代码示例展示其在实际应用场景中的使用方式,包括界面美化、导航与模块管理等方面。同时对它们的优势与局限性进行了…...

【超详细】Git的基本概念和基本使用方式

Git是程序开发中非常重要的工具&#xff0c;是一种分布式版本控制系统&#xff0c;可用于管理和追踪软件开发过程中的变化。那么关于Git的基本操作你知道吗&#xff1f;下面是Git的基本概念和使用方式的解释&#xff1a; 仓库&#xff08;Repository&#xff09;&#xff1a;Gi…...

【数据结构】单链表的使用

单链表的使用 1、基本概念2、链表的分类3、链表的基本操作a、单链表节点设计b、单链表初始化c、单链表增删节点**节点头插&#xff1a;****节点尾插&#xff1a;****新节点插入指定节点后&#xff1a;**节点删除&#xff1a; d、单链表修改节点e、单链表遍历&#xff0c;并打印…...

外键约束的应用层维护

1.前言 一般来说 对于不同表格之间的属性约束 我们通常直接使用数据库已经实现好的外键来完成 但是数据库底层实现的外键他的性能很差 这是因为在执行数据库修改操作时 他需要遍历其他所有的表来找出其中可能相关联的属性 一并进行数据库修改(应用层的维护则只需要遍历所有关联…...

springboot整合log4j2日志框架1

目录 一 log4j基本知识 1.1 log4j的日志级别 1.2 log4j的日志文件结构* 1.2.1 概述 1.2.2 详解 1.3 log4j的日志格式化api 1.3.1 api详解 1.3.2 演示案例 1.3.3 演示案例 1.4 log4j中onmatch和onmismatch的区别* 1.4.1 案例 1.4.2 onmatch的api 1.5 logback&#x…...

06 - Django 视图view

HttpRequest 和 HttpResponse Django中的视图主要用来接受Web请求&#xff0c;并做出响应。 视图的本质就是一个Python中的函数 视图的响应分为两大类 以Json数据形式返回(JsonResponse)以网页的形式返回 重定向到另一个网页 (HttpResponseRedirect)错误视图(4XX,5XX) (Htt…...

基于云计算的资源管理系统

基于云计算的资源管理系统是一种将云计算技术与资源管理技术相结合&#xff0c;以实现资源高效利用和管理的系统。以下是对该系统的详细分析&#xff1a; 一、系统概述 云计算是一种基于网络的计算模式&#xff0c;通过将计算资源和数据存储在云端服务器上&#xff0c;使用户…...

从0入门自主空中机器人-3-【环境与常用软件安装】

关于本课程&#xff1a; 本次课程是一套面向对自主空中机器人感兴趣的学生、爱好者、相关从业人员的免费课程&#xff0c;包含了从硬件组装、机载电脑环境设置、代码部署、实机实验等全套详细流程&#xff0c;带你从0开始&#xff0c;组装属于自己的自主无人机&#xff0c;并让…...

electron node-api addon开发

解决方案入口 拷贝日志以及json等第三方源码 增加包含目录 编写接口 默认模板已经有一个回调函数了 照葫芦画瓢就行 其中几个重要的点要注意 1.参数传入 比如如下的例子&#xff1a; 头文件定义&#xff1a; public:下增加 Napi::Value StartAnswer (const Napi::Callb…...

如何在嵌入式系统或计算机系统中验证boot程序

在嵌入式系统或计算机系统中&#xff0c;验证boot程序&#xff08;引导程序&#xff09;的正确性至关重要&#xff0c;因为它负责初始化系统硬件、加载操作系统内核&#xff0c;并设置系统环境。以下是一些常用的验证boot程序的方法&#xff1a; 一、硬件验证 示波器与逻辑分…...

scala基础学习_运算符

文章目录 scala运算符算术运算符关系运算符逻辑运算符位运算符其他运算符赋值运算符 scala运算符 在 Scala 中&#xff0c;运算符通常被定义为方法。这意味着你可以将运算符视为对象上的方法调用。以下是一些常用的运算符及其对应的操作&#xff1a; 算术运算符 &#xff1a…...

【ANGULAR网站开发】初始环境搭建

1. 初始化angular项目 1.1 创建angular项目 需要安装npm和nodejs&#xff0c;这边不在重新安装 直接安装最新版本的angular npm install -g angular/cli安装指定大版本的angular npm install -g angular/cli181.2 启动angular 使用idea启动 控制台启动 ng serve启动成功…...

【Java】面试题 并发安全 (2)

文章目录 可重入锁&#xff08;ReentrantLock&#xff09;知识总结1. 可重入锁概念与特点2. 基本语法与使用注意事项3. 底层实现原理4. 面试回答要点 synchronized与lock的区别死锁相关面试题讲解死锁产生的四个条件ConcurrentHashMap2. JDK1.7的ConcurrentHashMap结构添加数据…...

springboot启动不了 因一个spring-boot-starter-web底下的tomcat-embed-core依赖丢失

这个包丢失了 启动不了 起因是pom中加入了 <tomcat.version></tomcat.version>版本指定&#xff0c;然后idea自动编译后&#xff0c;包丢了&#xff0c;删除这个配置后再也找不回来&#xff0c; 这个包正常在 <dependency><groupId>org.springframe…...

React 组件的通信方式

在 React 应用开发中&#xff0c;组件之间的通信是构建复杂用户界面和交互逻辑的关键。正确地实现组件通信能够让我们的应用更加灵活和易于维护。以下是几种常见的 React组件通信方式。 一、父子组件通信 1. 通过 props 传递数据&#xff08;父组件向子组件传递数据&#xff0…...

WAV文件双轨PCM格式详细说明及C语言解析示例

WAV文件双轨PCM格式详细说明及C语言解析示例 一、WAV文件双轨PCM格式详细说明1. WAV文件基本结构2. PCM编码方式3. 双轨PCM格式详细说明二、C语言解析WAV文件的代码示例代码说明一、WAV文件双轨PCM格式详细说明 WAV文件是一种用于存储未压缩音频数据的文件格式,广泛应用于音频…...

【ES6复习笔记】数值扩展(16)

介绍 在 JavaScript 中&#xff0c;数值扩展提供了一些额外的功能&#xff0c;使得处理数值变得更加方便。本教程将介绍一些常用的数值扩展方法和属性。 1. Number.EPSILON Number.EPSILON 是 JavaScript 表示的最小精度。它的值接近于 2.2204460492503130808472633361816E-…...

百度热力图数据日期如何选择

目录 1、看日历2、看天气 根据研究内容定&#xff0c;一般如果研究城市活力的话&#xff0c;通常会写“非重大节假日&#xff0c;非重大活动&#xff0c;非极端天气等”。南方晴天不多&#xff0c;有小雨或者中雨都可认为没有影响&#xff0c;要不然在南方很难找到完全一周没有…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...