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

(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 个任务排成一个序列在一台机器上等待执行&#xff0c;它们的顺序不得改变。 机器会把这 N 个任务分成若干批&#xff0c;每一批包含连续的若干个任务。 从时刻 0 开始&#xff0c;任务被分批加工&#xff0c;执行第 i 个任务所需的时间是 Ti。 另外&#x…...

Excel筛选后复制粘贴不连续问题的解决

一直以来都没好好正视这个问题认真寻求解决办法 终于还是被需求逼出来了&#xff0c;懒人拯救世界[doge] 一共找到两个方法&#xff0c;个人比较喜欢第二种&#xff0c;用起来很方便 Way1&#xff1a;CtrlG定位可见单元格后使用vlookup解决&#xff08;感觉不定位直接公式向下…...

【SCSS变量】$ | | var | @for | @include | @function | @each 等常用方法使用

SCSS优点&#xff1a;编写清晰、无冗余、语义化的CSS&#xff0c;减少不必要的重复工作 1、变量声明&#xff08;$&#xff09;和使用2、使用 & 代替父元素3、在HTML中使用 :style{--name: 动态值}自定义属性&#xff0c;在SCSS中用var(--name)函数绑定动态变量值&#xff…...

iOS 17 及 Xcode 15.0 Beta7 问题记录

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

docker-maven-plugin直接把镜像推到私有仓库

接着上篇 推送到本地docker 我们已经把服务做成镜像推到docker&#xff0c;也可以通过docker login 私有地址&#xff0c;去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---订阅模型分类

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

pycharm添加虚拟环境以及虚拟环境安装pytorch

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

Git企业开发控制理论和实操-从入门到深入(三)|分支管理

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...

【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. 统计参与通信的服务器 中等 这里有一幅服务器分布图&#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中&#xff0c;1 表示单元格上有服务器&#xff0c;0 表示没有。 如果两台服务器位于同一行或者同一列&#xff0c;我们就认为它们之间可以进行通信。 请…...

Linux TCP协议——三次握手,四次挥手

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

人机对抗智能-部分可观测异步智能体协同(POAC)

环境链接&#xff1a;数据中心-人机对抗智能 (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失败 参考文章&#xff1a; 安装torch0.4.1的神坑_torch0.4.1_DEMO_Tian的博客-CSDN博客 co…...

数学——七桥问题——图论

当涉及数学&#xff0c;有很多不同的话题可以讨论。你是否有特定的数学领域、概念或问题想要了解更多&#xff1f;以下是一些常见的数学领域和主题&#xff0c;你可以选择一个或者告诉我你感兴趣的具体内容&#xff0c;我将很乐意为你提供更多信息&#xff1a; 代数学&#xff…...

python 模块lxml 处理 XML 和 HTML 数据

xpath&#xff1a;https://blog.csdn.net/randy521520/article/details/132432903 一、安装 XPath (XML Path Language) 是一门在 HTML\XML 文档中查找信息的语言&#xff0c;可用来在 HTML\XML 文档中对元素和属性进行遍历。 pip install lxml二、使用案例 from lxml impo…...

SpringBoot 统⼀功能处理

统⼀功能处理 1. 拦截器2. 统⼀异常处理3. 统⼀数据返回格式 1. 拦截器 Spring 中提供了具体的实现拦截器&#xff1a;HandlerInterceptor&#xff0c;拦截器的实现分为以下两个步骤&#xff1a; 创建⾃定义拦截器&#xff0c;实现 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 需要升级到&#xff1a; workbench 8.0 https://dev.mysql.com/downloads/workbench/...

Qt Scroll Area控件设置,解决无法显示全部内容,且无法滚动显示问题。

前言&#xff0c;因为要显示很多条目的内容&#xff0c;原来是用Vertical Layout控件里面嵌套Horizontal layout显示了很多行控件&#xff0c;发现最简单的方法就是使用滚动条控件&#xff0c;但是无论如何调整需要滚动的控件高度&#xff0c;始终无法滚动显示内容。也就是说添…...

【Java架构-包管理工具】-Maven私服搭建-Nexus(三)

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

Docker 离线安装指南

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

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

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服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

如何理解 IP 数据报中的 TTL?

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

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...