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 网络安…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
