动态规划——带权活动选择
| 带权活动选择 | ||
|---|---|---|
| Time Limit: 3000 MS | Memory Limit: 1000 KB | |
Description
给定n个活动,活动ai表示为一个三元组(si,fi,vi),其中si表示活动开始时间,fi表示活动的结束时间,vi表示活动的权重,
si<fi。带权活动选择问题是选择一些活动,使得任意被选择的两个活动ai和aj执行时间互不相交,即区间[si,fi)与[sj,fj)
互不重叠,并且被选择的活动的权重和最大。请设计一种方法求解带权活动选择问题。
Input
第一行输入M(M<=10)表示有M组数据。每组数据输入整数N(N<=10000), 接下来输入N个活动。
Output
输出M行正整数,第i行表示第i组数据的能够选择活动最大权值和。
Sample Input
2
5
7 9 9
7 8 1
6 7 9
6 8 5
4 9 9
5
4 7 9
3 4 4
7 8 8
8 9 6
4 5 9
Sample Output
18
27
二、解题思路
先将活动按照结束时间进行排序,
三、代码示例
注意这里使用了sort函数进行排序,sort
#include <iostream>
#include <algorithm>
using namespace std;struct Activity {
int s, e, v;
};bool cmp(Activity a, Activity b) { return a.e < b.e;
}int main() {int m, n;cin >> m;while (m--) {cin >> n;int dp[10001] = { 0 };Activity activities[10001];for (int i = 1; i <= n; i++) {cin >> activities[i].s;cin >> activities[i].e;cin >> activities[i].v;}dp[0] = 0;activities[0].s = activities[0].e = activities[0].v = 0;sort(activities + 1, activities + n + 1, cmp);for (int i = 1; i <= n; i++) {for (int j = i - 1; j >= 0; j--) {//从前一个开始依次向前找结束时间在它开始时间之前的if (activities[j].e <= activities[i].s) {dp[i] = max(dp[i - 1], dp[j] + activities[i].v);break;}}}cout << dp[n] << endl;}return 0;
}
相关文章:
动态规划——带权活动选择
带权活动选择Time Limit: 3000 MSMemory Limit: 1000 KB Description 给定n个活动,活动ai表示为一个三元组(si,fi,vi),其中si表示活动开始时间,fi表示活动的结束时间,vi表示活动的权重, si<fi。带权活动选择问题是选择一些活…...
软考A计划-真题-分类精讲汇总-第十八章(面向对象程序设计)
点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例 👉关于作者 专注于Android/Unity和各种游戏开发技巧,以及各种资源分享&am…...
【C++ 入坑指南】(09)数组
文章目录 简介一维数组1. 定义2. 特点3. 用途4. 示例 二维数组1. 定义2. 用途3. 示例 简介 C 支持数组数据结构,它可以存储一个固定大小的相同类型元素的顺序集合。数组是用来存储一系列数据,但它往往被认为是一系列相同类型的变量。 一维数组 1. 定义…...
Vue.js
文章目录 Vue(前端框架)data基本语法v-bind(属性)v-if(条件)v-formethods事件v-model表单绑定todolist(添加删除展示内容,含上下移动)es6语法生命周期函数axios发送ajax请…...
博士毕业答辩流程 注意事项
前言:2023年5月17日14:00-17:00,与实验室其他同学一起旁听了本实验室的博士论文答辩。接下来,我对博士毕业答辩的大致流程进行简要介绍,并对个环节的注意事项进行总结归纳,供毕业生参考。 目录 1. 准备阶段2. 汇报期间…...
拼多多开放平台订单详情接口解析
API接口订单接口是指用于实现订单相关操作的程序接口。通过这个接口,用户可以实现创建、修改、查询和取消订单等功能。 常见的API接口订单接口包括: 创建订单接口,用于实现用户下单操作。 修改订单接口,用于修改已有订单信息。 …...
如何把ipa文件(iOS安装包)安装到iPhone手机上? 附方法汇总
苹果APP安装包ipa如何安装在手机上?很多人不知道怎么把ipa文件安装到手机上,这里就整理了苹果APP安装到iOS设备上的方式,仅供参考 苹果APP安装包ipa如何安装在手机上?使用过苹果手机的人应该深有感触,那就是苹果APP安…...
由浅入深了解 深度神经网络优化算法
CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 导言 优化是从一组可用的备选方案中选择最佳方案。优化无疑是深度学习的核心。基于梯度下降的方法已经成为训练深度神经网络的既定方法。 在最简单的情况下,优化问题包括通过系统地从允许集合中…...
LIN-报文结构
文章目录 协议规范一、字节场二、报文头(HEADER FIELDS)同步间隔(synchronisation break)同步场(SYNCH FIELD)标识符场(IDENTIFIER FIELD) 三、数据场(DATE FIELDS)四、校…...
南京邮电大学通达学院2023c++实验报告(三)
题目 实验题目1 某公司财务部需要开发一个计算雇员工资的程序。该公司有3类员工,工资计算方式如下: (1)工人工资:每小时工资额(通过成员函数设定)乘以当月工作时数(通过成员函数设定),再加上工龄工资。 (2)销售员工资:每小时工资额(通过成员函数设定)乘以当月…...
ISO9000和ISO9001有哪些区别?
作为ISO标准体系的新手,ISO9000和ISO9001是第一个接触到的标准。有些人可能会含糊地表达包含关系的词语,但他们仍然无法真正理解它们。两者的关系是什么?有什么区别?事实上,两者的主要区别体现在以下三个方面: 第一&am…...
第7章异常、断言和曰志
Java和C异 在C中,throw说明符在运行时执行。Java在编译时执行。 处理错误 异常处理的任务就是将控制权从产生错误的地方转移到能够处理这种情况的错误处理器。 如果由于出现错误而使得某些操作没有完成,程序应该:返回到一种安全状态&#…...
springboot读取和写入csv文件数据
前言 csv格式的表格,和xls以及xlsx格式的表格有一些不同,不能够直接用处理xls的方式处理csv; 以下我将介绍如何读取并写入csv数据 准备工作 要处理csv格式的表格数据,我们首先需要引入pom.xml的依赖 <dependency><art…...
【产品经理】工作交接
一、前言 相信大家对这样的场景一定不陌生:有一天去找某个业务的负责人,突然被告知调岗了,或是辞职了,更坏的情况是,甚至完全找不到相关人员了,直接导致工作搁置了。这种情况,你应该多少会感到…...
Springer期刊 latex投稿经验分享
Springer Nature期刊的latex模板下载: Download the journal article template package 以MTAP为例(修改之后对修订稿的投递过程) 第一步:将您的文章提交到适当的期刊轨道或特刊。 如有必要,从下拉菜单中更改您提交的文章类型。 然后点击Proceed 第二步: 与您提交的先前修…...
Python 文件读取的练习
读取文本文件 给定一个名为 ‘example.txt’ 的文本文件,编写一段Python代码,读取文件并打印其内容。 行数统计 给定一个名为 ‘example.txt’ 的文本文件,编写一段Python代码,计算文件中的行数。 单词统计 给定一个名为 ‘exam…...
Redis:主从复制_通过此功能实现对内存上的数据更好的保护
什么是主从复制? 简单的意义上来讲就是一个主人带着几个奴隶,奴隶的全部都是主人给他的,刚开始的时候奴隶是一无所有,是主人将自己的一部分给到奴隶了。因此奴隶翻身了,变得有钱了,也就是有一定价值了&…...
LoRA:大模型的低秩自适应微调模型
对于大型模型来说,重新训练所有模型参数的全微调变得不可行。比如GPT-3 175B,模型包含175B个参数吗,无论是微调训练和模型部署,都是不可能的事。所以Microsoft 提出了低秩自适应(Low-Rank Adaptation, LoRA),它冻结了预…...
拼多多买家如何导出“个人中心”订单信息
经常在拼多多买东西,有时候需要把订单的物流信息导出来,方便记录和统计。现介绍如何使用dumuz工具来实现批量下载拼多多订单。 应用功能描述 模拟人工操作拼多多"个人中心-我的订单”订单网页,批量查询获取拼多多自己买的商品的订单数…...
11.计算机基础-计算机网络面试题—基础知识
本文目录如下: 计算机基础-计算机网络 面试题一、基础知识简述 TCP 和 UDP 的区别?http 与 https的区别?Session 和 Cookie 有什么区别?详细描述一下 HTTP 访问一个网站的过程?https 是如何实现加密的?URL是什么&…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...
【WebSocket】SpringBoot项目中使用WebSocket
1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖,添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...
