(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安装…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...