P2889 [USACO07NOV] Milking Time S
题目大意
有 N N N 个小时可以挤奶。其中有 m m m 个时间段可以给 Bessis 奶牛挤奶。第 i i i 个时间段为 s i s_i si ~ t i t_i ti,可以获得 E f f i Eff_i Effi 滴奶。每次挤完奶后,人都要休息 R R R 小时。最后问,一共能挤出多少滴奶。
双重选择分析
休息 R R R 小时可以归为挤奶时间段内。即,第 i i i 段挤奶的时间段为 s i s_i si ~ t i = t i + R t_i=t_i+R ti=ti+R。
设挤奶的最佳方案为:
{ a 1 , a 2 , . . . , a k } \{a_1,a_2,...,a_k\} {a1,a2,...,ak},其中 a i a_i ai 是第 i i i 个挤奶的时间段编号。同时满足 s a 2 ≥ t a 1 s_{a_2}\ge t_{a_1} sa2≥ta1, s a 3 ≥ t a 2 s_{a_3}\ge t_{a_2} sa3≥ta2,以此类推。
显然,为了更好的选奶牛,要对奶牛按 t i t_i ti 进行排列。
对 a k a_k ak 进行双重选择分析:
-
当 a k = m a_k=m ak=m,方案变为 { a 1 , a 2 , . . . , a k − 1 , m } \{a_1,a_2,...,a_{k-1},m\} {a1,a2,...,ak−1,m}方案的属性:
- 奶量。原方案的奶量 = 子方案的奶量 + E f f m Eff_m Effm。由于,原方案求的是最大奶量,所以子方案求解的也是最大奶量。
- 可以选择的时间段范围。子方案可以选择的范围为 1 ~ m − 1 m-1 m−1。
- 奶牛最大的挤奶结束时间。子方案奶牛最大的挤奶结束时间为 s m s_m sm。
综上,子方案反映的问题为,从 1 ~ m − 1 m-1 m−1 个时间段中,挤奶结束时间最大为 s m s_m sm 的最大奶量问题。
-
当 a k ≠ m a_k≠m ak=m,方案不变。
方案的属性:- 奶量。原方案的奶量 = 子方案的奶量。
- 可以选择的时间段范围。子方案可以选择的范围为 1 ~ m − 1 m-1 m−1。
- 奶牛最大的挤奶结束时间。子方案奶牛最大的挤奶结束时间为 N N N。
综上,子方案反映的问题为,从 1 ~ m − 1 m-1 m−1 个时间段中,挤奶结束时间最大为 N N N 的最大奶量问题。
综上,原问题的状态描述为 d p m , N dp_{m,N} dpm,N状态转移式为 d p m , N = max ( d p m − 1 , s n + E f f m , d p m − 1 , N ) dp_{m,N} = \max(dp_{m-1,s_n}+Eff_m,dp_{m-1,N}) dpm,N=max(dpm−1,sn+Effm,dpm−1,N)
将其一般化可得 d p i , j = max ( d p i − 1 , s i + E f f i , d p i − 1 , j ) dp_{i,j}=\max(dp_{i-1,s_i}+Eff_i,dp_{i-1,j}) dpi,j=max(dpi−1,si+Effi,dpi−1,j)需要注意的是:第一种情况只有当 t i ≤ j t_i\le j ti≤j 的时候才成立。
这样做,最终的时间复杂度、空间复杂度都为 O ( n m ) O(nm) O(nm),只能拿到 70 分。
示例程序
#include<iostream>
#include<algorithm>using namespace std;const int N = 1e3 + 10;struct node{int s,t,eff;bool operator < (const node &p)const{return t < p.t;}
}cow[N];int dp[N][N * 100];int main(){int n,m,r;cin >> n >> m >> r;n += r;for(int i = 1; i <= m; i++){cin >> cow[i].s >> cow[i].t >> cow[i].eff;cow[i].t = cow[i].t + r;}sort(cow + 1,cow + m + 1);for(int i = 0; i <= n; i++){if(i >= cow[1].t) dp[1][i] = cow[1].eff;else dp[1][i] = 0;}for(int i = 2; i <= m; i++){for(int j = 0; j <= n; j++){if(j >= cow[i].t){dp[i][j] = dp[i - 1][cow[i].s] + cow[i].eff;}dp[i][j] = max(dp[i][j],dp[i - 1][j]);}}cout << dp[m][n];return 0;
}
相关文章:
P2889 [USACO07NOV] Milking Time S
题目大意 有 N N N 个小时可以挤奶。其中有 m m m 个时间段可以给 Bessis 奶牛挤奶。第 i i i 个时间段为 s i s_i si ~ t i t_i ti,可以获得 E f f i Eff_i Effi 滴奶。每次挤完奶后,人都要休息 R R R 小时。最后问,一共能挤出…...
基于Spring Boot的健康医院门诊在线挂号系统设与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
PyTorch-基础(CUDA、Dataset、transforms、卷积神经网络、VGG16)
PyTorch-基础 环境准备 CUDA Toolkit安装(核显跳过此步骤) CUDA Toolkit是NVIDIA的开发工具,里面提供了各种工具、如编译器、调试器和库 首先通过NVIDIA控制面板查看本机显卡驱动对应的CUDA版本,如何去下载对应版本的Toolkit工…...
复现论文:DPStyler: Dynamic PromptStyler for Source-Free Domain Generalization
论文:[2403.16697] DPStyler: Dynamic PromptStyler for Source-Free Domain Generalization github: TYLfromSEU/DPStyler: DPStyler: Dynamic PromptStyler for Source-Free Domain Generalization 论文: 这篇论文还是在PromptStyler:Prompt-driven Style Gener…...
6.将cr打包成网络服务|使用postman进行测试|编写oj_server的服务路由功能(C++)
将cr打包成网络服务 compile_server.cc #include "compile_run.hpp" #include "../comm/httplib.h"using namespace ns_compile_and_run; using namespace httplib;//编译服务随时可能被多个人请求,必须保证传递上来的code,形成源…...
基于SpringBoot + Vue的共享汽车(单车)管理系统设计与实现+毕业论文+开题报告+指导搭建视频
本系统包含管理员、用户两个角色。 管理员角色:个人中心管理、用户管理、投放地区管理、汽车信息管理、汽车投放管理、汽车入库管理、使用订单管理、汽车归还管理。 用户角色:注册登录、汽车使用下单、汽车归还。 本共享汽车管理系统有管理员和用户。管…...
Day54(补)【AI思考】-SOA,Web服务以及无状态分步解析与示例说明
文章目录 **SOA,Web服务以及无状态**分步解析与示例说明**分步解析与示例说明****1. 核心概念解析****2. 为什么说SOA与Web服务是“正交的”?****3. 架构风格 vs. 实现技术****4. 接口(Interface)的核心作用****5. Web服务的“被认…...
回溯算法之组合和排列问题
文章目录 1.什么是回溯算法2.回溯算法解题步骤3.回溯算法解决组合问题4.回溯算法解决排列问题 1.什么是回溯算法 回溯算法是一种通过尝试所有可能的解决方案来解决问题的算法策略,它通常用于求解组合优化、排列组合、路径搜索等类型的问题,是一种暴力求解的算法。 2…...
gihub上适合练手的Python项目
GitHub 上有许多适合练手的 Python 项目,涵盖了从初学者到中级开发者的不同难度级别。以下是一些推荐的项目类型和具体示例,帮助你提升 Python 编程技能: 1. 基础项目 适合初学者,帮助掌握 Python 基础语法和常用库。 示例项目&…...
解锁CSnakes:.NET与Python的融合魔法
一、引言 在软件开发的广袤领域中,我们常常面临各种复杂的业务需求和技术挑战。不同的编程语言犹如各具特色的工具,它们在不同的场景下展现出独特的优势。例如,C# 以其强大的类型系统和丰富的类库,在企业级应用开发中占据重要地位…...
Python常见面试题的详解16
1. 如何强行关闭客户端和服务器之间的连接? 在网络编程中,有时需要强行中断客户端和服务器之间的连接。对于基于 TCP 协议的连接,由于其面向连接的特性,需要采取特定的步骤来确保连接被正确关闭;而 UDP 是无连接协议&a…...
建筑兔零基础自学python记录29|实战词云可视化项目——分人物阵营词云(上)7
我们在上次情感分析的基础上,不分积极消极,按文本中人物的阵营分为3队。可以猜想按照积极消极分类是有现成的feeling可以分析,但人物阵营却是没有现成资料,需要额外给出信息的。 图1 图2 上面两图的文字大小和数量有区别…...
Vi 编辑器基本使用指南
一、Vi 编辑器的启动与退出 启动 Vi 编辑器 在终端中,输入vi加上要编辑的文件名,如vi example.txt,如果example.txt存在,Vi 编辑器会打开该文件;若不存在,则会创建一个新的空文件并打开。如果只输入vi&am…...
22、《Spring Boot消息队列:RabbitMQ延迟队列与死信队列深度解析》
Spring Boot消息队列实战:RabbitMQ延迟队列与死信队列深度解析 引言 在现代分布式系统中,消息队列承担着解耦、削峰填谷和异步通信的重要职责。本文将深入探讨Spring Boot与RabbitMQ的整合应用,重点解析延迟队列与死信队列的实现原理及实战…...
linux 命令+相关配置记录(持续更新...)
linux 命令记录相关配置记录 磁盘切换 cd D:#这里表示切换到D盘查看wsl 安装的linux 子系统 wsl --list -vwsl 卸载 linux 子系统 wsl --unregister -xxx # xxx 表示子系统的名字备份Linux 子系统 导出 wsl --export xxx yyy # xxx 表示子系统的名字 yyy 表示压…...
ssh工具
文章目录 ssh简介ssh远程连接Linux下使用SSH安装安装ssh服务端安装ssh客户端 命令启动重启查看ssh的状态 ssh 配置文件ssh连接地址 配置文件基本配置注意通配符心跳和密钥ssh的Include跳板 ProxyJump内网穿透 Windows下使用SSH安装ssh 配置文件ssh连接地址 配置文件 ssh简介 s…...
LLM大语言模型私有化部署-使用Dify的工作流编排打造专属AI诗词数据分析师
背景 前面的文章通过 Ollama 私有化部署了 Qwen2.5 (7B) 模型,然后使用 Docker Compose 一键部署了 Dify 社区版平台。 LLM大语言模型私有化部署-使用Dify与Qwen2.5打造专属知识库:在 Dify 平台上,通过普通编排的方式,创建了基于…...
Windows 图形显示驱动开发-WDDM 3.2-自动显示切换(二)
在 GPU0 和 GPU1 之间共享数据 在某些情况下,也许可以在某些时候带来更好的用户体验: GPU0 和 GPU1 来自同一个 IHV。GPU0 可以将操作系统无法解读的显示配置相关信息传递给 GPU1。 数据 Blob 由 GUID 描述,如果 GPU1 的驱动程序能理解数据…...
基于CentOS7安装kubesphere和Kubernetes并接入外部ES收集日志
一、修改所有节点主机名 主节点就修改成master hostnamectl set-hostname master 然后输入bash刷新当前主机名 工作节点1就修改成node1 hostnamectl set-hostname node1 然后输入bash刷新当前主机名 二、全部节点安装依赖并同步时间 yum -y install socat conntrack ebta…...
软考教材重点内容 信息安全工程师 第17章 网络安全应急响应技术原理与应用
17.1 网络安全应急响应概述 网络安全应急响应是针对潜在发生的网络安全事件而采取的网络安全措施。 17.1.1 网络安全应急响应概念 网络安全应急响应是指为应对网络安全事件,相关人员或组织机构对网络安全事件进行监测、预警、分析、响应和恢复等工作。 17.2.3 网络安…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
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 …...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
