(AcWing) 任务安排(I,II,III)
任务安排I:
有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。
机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。
从时刻 0 开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。
另外,在每批任务开始前,机器需要 S 的启动时间,故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。
一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。
也就是说,同一批任务将在同一时刻完成。
每个任务的费用是它的完成时刻乘以一个费用系数 Ci。
请为机器规划一个分组方案,使得总费用最小。
输入格式
第一行包含整数 N。
第二行包含整数 S。
接下来 N 行每行有一对整数,分别为 Ti 和 Ci,表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。
输出格式
输出一个整数,表示最小总费用。
数据范围
1≤N≤5000,
0≤S≤50,
1≤Ti,Ci≤100
输入样例:
5
1
1 3
3 2
4 3
2 3
1 4
输出样例:
153
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 5010;
ll sumt[N],sumc[N],f[N];
//sumt[N]时间前缀和
//sumc[N]费用前缀和
//f[N]是将前i个任务处理完的所有方案的集合
ll n,s;int main()
{cin>>n>>s;for(int i=1;i<=n;i++){int t,c;cin>>t>>c;sumt[i] = t + sumt[i-1];sumc[i] = c + sumc[i-1];}memset(f,0x3f,sizeof f);//预防下面求最小值出错,先初始化为无穷大f[0] = 0;//前0个任务处理完的方案数自然为0for(int i=1;i<=n;i++){for(int j=0;j<i;j++){f[i] = min(f[i],f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]));}}cout<<f[n]<<endl;return 0;
}
AcWing 300. 任务安排1【线性DP+费用提前计算思想】 - AcWing
任务安排II:斜率优化DP
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;typedef long long ll;
const int N = 300010;
int n,s;
ll c[N],t[N],f[N],q[N];int main()
{cin>>n>>s;//读入数据计算时间和代价的前缀和for(int i=1;i<=n;i++){int a,b;cin>>a>>b;c[i] = c[i-1]+b;t[i] = t[i-1]+a;}int hh=0,tt=0; //hh是队头,tt的队尾q[0] = 0; //数组q表示的是队列,队列一开始存在(0,0)点for(int i=1;i<=n;i++){//将小于等于目标斜率的点全部删掉 (删除的是组成斜率的两个点中的第一个点)while(hh<tt&&(f[q[hh+1]]-f[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;//对头的元素就是我们所求的f[i]最小的点int j = q[hh];//代入公式f[i] = f[j] - (t[i]+s)*c[j]+t[i]*c[i] + s*c[n];//计算完后插入新的点,插入前应该将队尾所有不在凸包上的点均删掉while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;q[++tt] = i;}cout<<f[n]<<endl;
}
AcWing 301. 任务安排2【斜率优化DP模板】 - AcWing
相关文章:

(AcWing) 任务安排(I,II,III)
任务安排I: 有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。 机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。 从时刻 0 开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。 另外&#x…...
Excel筛选后复制粘贴不连续问题的解决
一直以来都没好好正视这个问题认真寻求解决办法 终于还是被需求逼出来了,懒人拯救世界[doge] 一共找到两个方法,个人比较喜欢第二种,用起来很方便 Way1:CtrlG定位可见单元格后使用vlookup解决(感觉不定位直接公式向下…...

【SCSS变量】$ | | var | @for | @include | @function | @each 等常用方法使用
SCSS优点:编写清晰、无冗余、语义化的CSS,减少不必要的重复工作 1、变量声明($)和使用2、使用 & 代替父元素3、在HTML中使用 :style{--name: 动态值}自定义属性,在SCSS中用var(--name)函数绑定动态变量值ÿ…...

iOS 17 及 Xcode 15.0 Beta7 问题记录
1、iOS 17 真机调试问题 iOS 17之后,真机调试Beta版本必须使用Beta版本的Xcode来调试,用以前复制DeviceSupport 方式无法调试,新的Beta版本Xcode中,已经不包含 iOS 17目录。如下图: 解决方案: 1&#x…...

docker-maven-plugin直接把镜像推到私有仓库
接着上篇 推送到本地docker 我们已经把服务做成镜像推到docker,也可以通过docker login 私有地址,去push。麻烦 直接上代码 1、pom改动 <properties><docker.registry>eco-registry.XXX.com</docker.repostory><docker.registry…...
2023年机器学习项目—布匹缺陷检测
2023年机器学习项目———布匹缺陷检测 测试环境: CPU : 12th Gen Intel Core™ i7-12700H 2.70 GHz GPU : NVIDIA RTX3070Ti RAM : 32GB Matlab R2020a (Deep Learning Tools) 注 :Data文件过大 未上传 一.神经网络概述 1. 卷积神经网络概念 人工神经网络(Artific…...

RabbitMQ---订阅模型分类
订阅模型分类 在之前的模式中,我们创建了一个工作队列。 工作队列背后的假设是:每个任务只被传递给一个工作人员。 在这一部分,我们将做一些完全不同的事情 - 我们将会传递一个信息给多个消费者。 这种模式被称为“发布/订阅”。 订阅模型示意…...

pycharm添加虚拟环境以及虚拟环境安装pytorch
file、settings、interpreter、add interpreter、add local interpreter 记住不要勾选inherit,不然会把主环境的东西继承到虚拟环境。 创建前可以先点existing看看有没有已经建好的虚拟环境 有的时候pycharm有问题,创建了虚拟环境没有显示。找一个.py文…...

Git企业开发控制理论和实操-从入门到深入(三)|分支管理
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...

【VsCode】SSH远程连接Linux服务器开发,搭配cpolar内网穿透实现公网访问(1)
文章目录 前言1、安装OpenSSH2、vscode配置ssh3. 局域网测试连接远程服务器4. 公网远程连接4.1 ubuntu安装cpolar内网穿透4.2 创建隧道映射4.3 测试公网远程连接 5. 配置固定TCP端口地址5.1 保留一个固定TCP端口地址5.2 配置固定TCP端口地址5.3 测试固定公网地址远程 前言 远程…...

LC-1267. 统计参与通信的服务器(枚举 + 计数)
1267. 统计参与通信的服务器 中等 这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。 请…...

Linux TCP协议——三次握手,四次挥手
一、TCP协议介绍 TCP协议是可靠的、面向连接的、基于字节流的传输层通信协议。 TCP的头部结构: 源/目的端口号: 表示数据是从哪个进程来, 到哪个进程去;(tcp是传输层的协议,端与端之间的数据传输,在TCP和UDP协议当中不会体现出I…...

人机对抗智能-部分可观测异步智能体协同(POAC)
环境链接:数据中心-人机对抗智能 (ia.ac.cn)http://turingai.ia.ac.cn/data_center/show/10 1.环境配置 Ubuntu 20.04 Anaconda python版本3.6 1.1 安装torch0.4.1失败 参考文章: 安装torch0.4.1的神坑_torch0.4.1_DEMO_Tian的博客-CSDN博客 co…...

数学——七桥问题——图论
当涉及数学,有很多不同的话题可以讨论。你是否有特定的数学领域、概念或问题想要了解更多?以下是一些常见的数学领域和主题,你可以选择一个或者告诉我你感兴趣的具体内容,我将很乐意为你提供更多信息: 代数学ÿ…...
python 模块lxml 处理 XML 和 HTML 数据
xpath:https://blog.csdn.net/randy521520/article/details/132432903 一、安装 XPath (XML Path Language) 是一门在 HTML\XML 文档中查找信息的语言,可用来在 HTML\XML 文档中对元素和属性进行遍历。 pip install lxml二、使用案例 from lxml impo…...
SpringBoot 统⼀功能处理
统⼀功能处理 1. 拦截器2. 统⼀异常处理3. 统⼀数据返回格式 1. 拦截器 Spring 中提供了具体的实现拦截器:HandlerInterceptor,拦截器的实现分为以下两个步骤: 创建⾃定义拦截器,实现 HandlerInterceptor 接⼝的 preHandle&…...
hadoop 报错 java.io.IOException: Inconsistent checkpoint fields
背景: 使用了格式化,导致首重了新的集群ID org.apache.hadoop.hdfs.server.common.InconsistentFSStateException: Directory /work1/home/hadoop/dfs/data/current/BP-1873526852-172.16.21.30-1692769875005 is in an inconsistent state: namespaceID is incompatible with …...

workbench连接MySQL8.0错误 bad conversion 外部组件 异常
阿里云搭建MySQL实用的版本是8.0 本地安装的版本是: workbench 6.3 需要升级到: workbench 8.0 https://dev.mysql.com/downloads/workbench/...

Qt Scroll Area控件设置,解决无法显示全部内容,且无法滚动显示问题。
前言,因为要显示很多条目的内容,原来是用Vertical Layout控件里面嵌套Horizontal layout显示了很多行控件,发现最简单的方法就是使用滚动条控件,但是无论如何调整需要滚动的控件高度,始终无法滚动显示内容。也就是说添…...

【Java架构-包管理工具】-Maven私服搭建-Nexus(三)
本文摘要 Maven作为Java后端使用频率非常高的一款依赖管理工具,在此咱们由浅入深,分三篇文章(Maven基础、Maven进阶、私服搭建)来深入学习Maven,此篇为开篇主要介绍Maven私服搭建-Nexus 文章目录 本文摘要1. Nexus安装…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...