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.矩阵连(链)乘 问题描述 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 年度回顾:技术突破与未来的无限可能
原文:https://medium.com/polkadot-network/polkadot-roundup-mmxxiv-8d3e880dd637 作者:Gavin Wood 编译:OneBlock 🎄 各位波卡生态的 Buidler 们,圣诞快乐!在这个充满节日气氛的时刻,很高兴与…...
AduSkin、WPF-UI、Prism:WPF 框架全解析与应用指南
摘要: 本文深入探讨了 AduSkin、WPF-UI、Prism 这三个在 WPF 开发领域极具影响力的框架。详细阐述了每个框架的特点、核心功能、安装与配置过程,并通过丰富的代码示例展示其在实际应用场景中的使用方式,包括界面美化、导航与模块管理等方面。同时对它们的优势与局限性进行了…...
【超详细】Git的基本概念和基本使用方式
Git是程序开发中非常重要的工具,是一种分布式版本控制系统,可用于管理和追踪软件开发过程中的变化。那么关于Git的基本操作你知道吗?下面是Git的基本概念和使用方式的解释: 仓库(Repository):Gi…...
【数据结构】单链表的使用
单链表的使用 1、基本概念2、链表的分类3、链表的基本操作a、单链表节点设计b、单链表初始化c、单链表增删节点**节点头插:****节点尾插:****新节点插入指定节点后:**节点删除: d、单链表修改节点e、单链表遍历,并打印…...
外键约束的应用层维护
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请求,并做出响应。 视图的本质就是一个Python中的函数 视图的响应分为两大类 以Json数据形式返回(JsonResponse)以网页的形式返回 重定向到另一个网页 (HttpResponseRedirect)错误视图(4XX,5XX) (Htt…...
基于云计算的资源管理系统
基于云计算的资源管理系统是一种将云计算技术与资源管理技术相结合,以实现资源高效利用和管理的系统。以下是对该系统的详细分析: 一、系统概述 云计算是一种基于网络的计算模式,通过将计算资源和数据存储在云端服务器上,使用户…...
从0入门自主空中机器人-3-【环境与常用软件安装】
关于本课程: 本次课程是一套面向对自主空中机器人感兴趣的学生、爱好者、相关从业人员的免费课程,包含了从硬件组装、机载电脑环境设置、代码部署、实机实验等全套详细流程,带你从0开始,组装属于自己的自主无人机,并让…...
electron node-api addon开发
解决方案入口 拷贝日志以及json等第三方源码 增加包含目录 编写接口 默认模板已经有一个回调函数了 照葫芦画瓢就行 其中几个重要的点要注意 1.参数传入 比如如下的例子: 头文件定义: public:下增加 Napi::Value StartAnswer (const Napi::Callb…...
如何在嵌入式系统或计算机系统中验证boot程序
在嵌入式系统或计算机系统中,验证boot程序(引导程序)的正确性至关重要,因为它负责初始化系统硬件、加载操作系统内核,并设置系统环境。以下是一些常用的验证boot程序的方法: 一、硬件验证 示波器与逻辑分…...
scala基础学习_运算符
文章目录 scala运算符算术运算符关系运算符逻辑运算符位运算符其他运算符赋值运算符 scala运算符 在 Scala 中,运算符通常被定义为方法。这意味着你可以将运算符视为对象上的方法调用。以下是一些常用的运算符及其对应的操作: 算术运算符 :…...
【ANGULAR网站开发】初始环境搭建
1. 初始化angular项目 1.1 创建angular项目 需要安装npm和nodejs,这边不在重新安装 直接安装最新版本的angular npm install -g angular/cli安装指定大版本的angular npm install -g angular/cli181.2 启动angular 使用idea启动 控制台启动 ng serve启动成功…...
【Java】面试题 并发安全 (2)
文章目录 可重入锁(ReentrantLock)知识总结1. 可重入锁概念与特点2. 基本语法与使用注意事项3. 底层实现原理4. 面试回答要点 synchronized与lock的区别死锁相关面试题讲解死锁产生的四个条件ConcurrentHashMap2. JDK1.7的ConcurrentHashMap结构添加数据…...
springboot启动不了 因一个spring-boot-starter-web底下的tomcat-embed-core依赖丢失
这个包丢失了 启动不了 起因是pom中加入了 <tomcat.version></tomcat.version>版本指定,然后idea自动编译后,包丢了,删除这个配置后再也找不回来, 这个包正常在 <dependency><groupId>org.springframe…...
React 组件的通信方式
在 React 应用开发中,组件之间的通信是构建复杂用户界面和交互逻辑的关键。正确地实现组件通信能够让我们的应用更加灵活和易于维护。以下是几种常见的 React组件通信方式。 一、父子组件通信 1. 通过 props 传递数据(父组件向子组件传递数据࿰…...
WAV文件双轨PCM格式详细说明及C语言解析示例
WAV文件双轨PCM格式详细说明及C语言解析示例 一、WAV文件双轨PCM格式详细说明1. WAV文件基本结构2. PCM编码方式3. 双轨PCM格式详细说明二、C语言解析WAV文件的代码示例代码说明一、WAV文件双轨PCM格式详细说明 WAV文件是一种用于存储未压缩音频数据的文件格式,广泛应用于音频…...
【ES6复习笔记】数值扩展(16)
介绍 在 JavaScript 中,数值扩展提供了一些额外的功能,使得处理数值变得更加方便。本教程将介绍一些常用的数值扩展方法和属性。 1. Number.EPSILON Number.EPSILON 是 JavaScript 表示的最小精度。它的值接近于 2.2204460492503130808472633361816E-…...
百度热力图数据日期如何选择
目录 1、看日历2、看天气 根据研究内容定,一般如果研究城市活力的话,通常会写“非重大节假日,非重大活动,非极端天气等”。南方晴天不多,有小雨或者中雨都可认为没有影响,要不然在南方很难找到完全一周没有…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
