洛谷 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的医院挂号管理系统应运而生。该系统旨在通过信息化…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
