洛谷 P1868 饥饿的奶牛
原题
题目描述
有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。
现用汉语翻译为:
有 N 个区间,每个区间x,y 表示提供的x∼y 共y−x+1 堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。
输入格式
第一行一个整数 N。
接下来 N 行,每行两个数x,y,描述一个区间。
输出格式
输出最多能吃到的牧草堆数。
输入输出样例
输入 #1
3 1 3 7 8 3 4
输出 #1
5
说明/提示

解题思路
动态加二分。
构造一个结构体存储元素,然后按照r从小到大排序。
dp[i]=max(dp[i-1],dp[lower_bound(1,i,cow[i].l)]+cow[i].val)
lower_bound(二分查找) 最后一个没有和cow[i].l相交的元素,寻找到后取最大的那个区间。
AC代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1.5e5+5;
struct Cow{int l,r;int val;bool operator <(const Cow b){return r<b.r;}
}cow[N];
int n,dp[N];
int lower_bound(int l,int r,int k){int ans=0;while(l<r){int mid=(l+r)>>1;if(cow[mid].r<k) {ans=mid;l=mid+1;}else r=mid;}return ans;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&cow[i].l,&cow[i].r);cow[i].val=cow[i].r-cow[i].l+1; }sort(cow+1,cow+n+1);for(int i=1;i<=n;i++){dp[i]=max(dp[i-1],dp[lower_bound(1,i,cow[i].l)]+cow[i].val);}printf("%d",dp[n]);return 0;
}
相关文章:
洛谷 P1868 饥饿的奶牛
原题 题目描述 有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。 现用汉语翻译为: 有 N 个区间,每个区间x,y 表示提供的x∼y 共y−x1 堆优质牧草。你可以选择任意区间但不…...
Arco Design 之Table表格
此篇文章为table表格示例,包含列、data数据、展开、选中、自定义等相关属性 基础表格 <a-table :columns"columns1" :data"tableData1" />const columns1 [{ title: "编号", dataIndex: "no"},{ title: "名称…...
Python机器学习 模型
Python机器学习模型、回归预测模型、数据清洗、数据处理、数据挖掘、数据分析代做。 模型不仅限于线性回归、逻辑回归、决策树、SVM、随机森林、贝叶斯、XGBoost、LightGBM、CatBoost,聚类:K-Means、DBSCAN,机器学习都可。 时间序列分析&…...
基于 STM32 的 NAS私有云盘搭建:集成LwIP 协议、HTTP/HTTPS、WEB前端技术栈(代码示例)
项目概述 在本项目中,我们将搭建一个基于 STM32 的 NAS(网络附加存储)私盘,通过网络访问存储在外部 SATA 硬盘上的文件。该项目将使用 STM32 开发板、外接 SATA 硬盘、LwIP 协议栈以及 FATFS 文件系统来实现文件的上传、下载和管…...
蓝屏?死机?爆CPU?多开卡顿?你有关心过你的硬盘吗?
上来先叠甲 蓝屏、死机、爆cpu、多开卡顿,不一定是硬盘的问题,只是硬盘有问题都可能会引起这些现象,所以不要遇到这些问题就一定认为是硬盘的问题然后说我说的,只是给你一个排除问题的思路。本文会采用比较通俗所以不太专业的角度…...
Flutter开发报错error: unable to unlink old ‘pubspec.yaml‘: Invalid argument
背景:主分支master,然后每人1个分支,每次push到自己分支后,再提mr到master。 于是每次提交前要先git merge origin/master。 有时候会报这个错误,无法merge 原因:很简单,就是pubspec.yaml这个文…...
零基础进程最详解:进程状态、僵尸进程、孤儿进程、阻塞态、挂起态、进程切换、进程常用命令、进程创建、队列优先级
目录 强烈建议全文阅读!!! 强烈建议全文阅读!!! 强烈建议全文阅读!!! 一、进程状态 二、僵尸和孤儿进程 1、僵尸进程 Z(zombie) 2、孤儿进…...
Redis的分布式锁
目录 一、定义与原理 基于Redis的分布式锁 获取锁 释放锁 锁误删问题:因为key值一样,将别人的锁删掉了 锁误判问题二:判断锁和释放锁不是原子性的 Lua脚本 分布式锁:满足分布式系统或集群模式下多进程可见并且互斥的锁 分布式锁的优点…...
C++笔记---类和对象
1. 类的定义 类是C中的一种自定义类型,是某个具体事物或概念的抽象化代码表示,通过类的成员(变量函数/方法),可以表征出事物或概念的特征。 1.1 类定义的格式 class Stack { public:// 成员函数void Init(int n 4)…...
全国区块链职业技能大赛样题第9套后端源码
后端源码地址:https://blog.csdn.net/Qhx20040819/article/details/140746050 前端源码地址:https://blog.csdn.net/Qhx20040819/article/details/140746216 智能合约+数据库表设计:https://blog.csdn.net/Qhx20040819/article/details/140746646 项目预览 登录 用户管理...
3个功能强大的PDF转换工具,免费试用
给大家分享3个功能强大能满足更高需求的PDF转换工具,都提供免费的试用机会。 1.嗨动PDF编辑器 一款多功能的PDF编辑软件,集PDF阅读、PDF转换、PDF编辑功能为一体。支持转换的格式多样,转换速度快,转换后的排版和内容与原文保持一…...
表单修改数字输入框保留小数点
1.在表单设计打开修改的表单 2.打开需要修改的字段 3.按F12,进入“开发模式” 4.开启“开发者工具”左上角检索工具 开启:鼠标左键点击,当图标颜色为蓝色 关闭:鼠标左键点击,当图标颜色为灰色 5.鼠标移动到需要修改的…...
[VS Code扩展]写一个代码片段管理插件(一):介绍与界面搭建
文章目录 VS Code扩展机制项目搭建创建UI元素活动栏按钮主边栏视图主边栏工具栏按钮侧边栏右键菜单编辑器右键菜单 项目地址 [VS Code扩展]写一个代码片段管理插件(一):介绍与界面搭建[VS Code扩展]写一个代码片段管理插件(二&…...
vxe grid slots 用法
官方例子:Vxe Table v3.8 {field: num1,title: Num1,showHeaderOverflow: true,filters: [{ data: }],editRender: { autofocus: .my-input },slots: {// 使用插槽模板渲染default: num1_default,header: num1_header,footer: num1_footer,filter: num1_filter,edi…...
【网络】基于UDP协议的聊天室(第二篇)
目录 UDP服务器 UDP客户端 在C中,使用UDP协议进行网络通信通常涉及到socket编程。下面我将给出基于UDP的简单的客户端和服务器示例代码。这些示例将使用C标准库以及POSIX套接字接口(主要适用于Linux和类Unix系统)。如果你在使用Windows&…...
【SpringBoot3】场景整合(实战)
0 环境准备 0.0 云服务器 阿里云、腾讯云、华为云 服务器开通; 按量付费,省钱省心 安装以下组件:docker、redis、kafka、prometheus、grafana 下载windterm: https://github.com/kingToolbox/WindTerm/releases/download/2.5…...
【全网最全最详细】MYSQL 面试题大全(上)
目录 一、关系型数据库和非关系型数据库主要有哪些区别? 二、MYSQL的数据存储一定是基于硬盘的吗? 三、InnoDB和MyISAM有什么区别? 四、MyISAM的索引结构是怎么样的?存在的问题是什么? 五、char和varchar的区别? 六、MYSQL 5.x和8.0有什么区别? 七、为什么大厂不…...
【C语言】程序环境,预处理,编译,汇编,链接详细介绍,其中预处理阶段重点讲解
目录 程序环境 翻译环境 1. 翻译环境的两个过程 2. 编译过程的三个阶段 执行环境 预处理(预编译) 1. 预定义符号 2. #define 2.1 用 #define 定义标识符(符号) 2.2 用 #define 定义宏 2.3 #define 的替换规则 2.4 # 和 ## 的用法 2.5 宏和函数 2.6 #undef …...
人生低谷来撸C#--021 多线程
1、概念 线程 被定义为程序的执行路径。每个线程都定义了一个独特的控制流。如果您的应用程序涉及到复杂的和耗时的操作,那么设置不同的线程执行路径往往是有益的,每个线程执行特定的工作。 线程是轻量级进程。一个使用线程的常见实例是现代操作系统中…...
【优秀python django系统案例】基于python的医院挂号管理系统,角色包括医生、患者、管理员三种
随着信息技术的迅猛发展,传统的医院挂号管理方式面临着效率低下、排队时间长、信息不对称等诸多问题。这些问题不仅影响患者的就医体验,也加重了医院工作人员的负担。在此背景下,基于Python的医院挂号管理系统应运而生。该系统旨在通过信息化…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》
🧠 LangChain 中 TextSplitter 的使用详解:从基础到进阶(附代码) 一、前言 在处理大规模文本数据时,特别是在构建知识库或进行大模型训练与推理时,文本切分(Text Splitting) 是一个…...
