P1868 饥饿的奶牛
根据题意可以知道是一个动态规划,看完数据范围之后可以知道是一个线性DP。
解决方法有点类似于背包问题,枚举背包的每一个空间。
如果把坐标轴上每个点都看成一个块儿,只需要按顺序求出前 i 个块儿的最大牧草堆数,f[i] 就是前i的最大牧草堆数。
假如区间x, y 是一个牧草堆块儿,只需取 f[y - 1] 与 f[x - 1] + y - x + 1,前者就相当于这个堆块儿不取的情况下的最大数,后者相当于取当前堆块儿的最大数,取最大值即可。
因为枚举的是坐标轴上的所有位置,所以每一个位置的最大值都可以从上一个位置更新过来,如果当前位置为某个堆块儿的右端点,只需要判断当前堆块儿取不取即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define x first
//#define y second
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef struct{int x, y;
}aa;
const int mod = 1e9 + 7;
const int N = 3e6+ 10;
int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
int n, m;
int x, y;
vector<int> vec[N];
int f[N];inline void sovle()
{cin >> n;int r = 0;for(int i = 0; i < n; i ++) // 用vector可以使代码更加简洁,不过空间有点悬。这一题还是行的{int a, b;cin >> a >> b;vec[b].push_back(a - 1); // 记录当前右端点对应的左端点,减一有利于之后的计算。r = max(b, r); // 记录最大右端点}for(int i = 1; i <= r; i ++){f[i] = f[i - 1];for(auto j : vec[i]) //枚举以当前位置为右端点的所有堆块儿{f[i] = max(f[i], f[j] + i - j); // 通过状态转移方程来更新当前位置。}}cout << f[r] << endl; // 输出最大值
}signed main(void)
{IOS;int t = 1;
// cin >> t;while(t --) sovle();return 0;
}
相关文章:
P1868 饥饿的奶牛
根据题意可以知道是一个动态规划,看完数据范围之后可以知道是一个线性DP。 解决方法有点类似于背包问题,枚举背包的每一个空间。 如果把坐标轴上每个点都看成一个块儿,只需要按顺序求出前 i 个块儿的最大牧草堆数,f[i] 就是前i的…...
【软考系统架构设计师】2021年系统架构师综合知识真题及解析
本文主要分享2021年下半年系统架构师综合知识历年真题以及本人在做题时的所思所想。题目序号有点混乱,可忽略 【01】.某计算机系统页面大小为4K,进程P1的页面变换表如下图所示,看P1要访问数据的逻辑地址为十六进制1B1AH,那么该逻辑地址经过变…...
如何在忘记手机密码或图案时重置 Android 手机?
忘记手机密码或图案是 Android 用户一生中不得不面对的最令人沮丧的事情之一。恢复 Android 设备的唯一方法是在 Android 设备上恢复出厂设置。但许多用户不使用此方法,因为此过程会擦除您设备上可用的所有个人数据。 但是,有一种方法可以在不丢失任何数…...
LeetCode每日一题——2520. Count the Digits That Divide a Number
文章目录 一、题目二、题解 一、题目 2520. Count the Digits That Divide a Number Given an integer num, return the number of digits in num that divide num. An integer val divides nums if nums % val 0. Example 1: Input: num 7 Output: 1 Explanation: 7 di…...
论文阅读——DistilBERT
ArXiv:https://arxiv.org/abs/1910.01108 Train Loss: DistilBERT: DistilBERT具有与BERT相同的一般结构,层数减少2倍,移除token类型嵌入和pooler。从老师那里取一层来初始化学生。 The token-type embeddings and the pooler a…...
202212 青少年等级考试机器人实操真题三级
202212 青少年等级考试机器人实操真题三级 考试时间:60分钟 总分:100 及格分:60 一、问答题 (共1题,每题100分) 1、实际操作(共1题,共100分) 请考生在实操考试结束前将本题作答程序文件按“说明”要求完成上传。 1. 主…...
token正确不报错,token失效后却出现报跨域错误
1.今天在使用koajs开发项目时,突然发现前端配置axios的response获取不到后端定义的token失效内容了,取而代之的是出现了跨域的错误。 2. 我马上去查找koajs的跨域中间件配置,发现配置完好cors,token正确时,接口正常访问…...
STM32中除零运算,为何程序不崩溃?
在 C 语言中,除零运算会导致异常吗? 在 C 语言中,当一个数除以零时,会导致除法运算错误,通常表现为“除以零”错误或被称为“浮点异常”(floating-point exception)。 对于整数除法,…...
sprinbboot 2.7启动不生成日志文件
新增了一个springboot项目,通过idea 调试,并且在idea 的vm options中指定-Dlogging.configclasspath:logback-pro.xml 或者 -Dlogging.configclasspath:logback-dev.xml 都能正常生成对应的日志文件。 部署到测试环境以及生产环境,日志文件却…...
Kafka - 3.x 图解Broker总体工作流程
文章目录 Zk中存储的kafka的信息Kafka Broker总体工作流程1. broker启动后向zk中注册2. Controller谁先启动注册,谁说了算3. 由选举出来的Controller监听brokers节点的变化4. Controller决定leader选举5. Controller将节点信息上传到Zk中6. 其他Controller从zk中同步…...
APP自动化测试 ---- Appium介绍及运行原理
在面试APP自动化时,有的面试官可能会问Appium的运行原理,以下介绍Appium运行原理。 一、Appium介绍 1.Appium概念 Appium是一个开源测试自动化框架,可用于原生,混合和移动Web应用程序测试。它使用WebDriver协议驱动IOS…...
学习模板发布
学习目标: 提示:这里可以添加学习目标 例如: 一周掌握 Java 入门知识 学习内容: 提示:这里可以添加要学的内容 例如: 搭建 Java 开发环境掌握 Java 基本语法掌握条件语句掌握循环语句 学习时间&#x…...
Hive 视图和索引
1.视图 1.1 简介 Hive 中的视图和 RDBMS 中视图的概念一致,都是一组数据的逻辑表示,本质上就是一条 SELECT 语句的结果集。视图是纯粹的逻辑对象,没有关联的存储 (Hive 3.0.0 引入的物化视图除外),当查询引用视图时,Hive 可以将视图的定义与查询结合起来,例如将查询中的过…...
EtherCAT主站SOEM-- 0 SOEM下载编译及文件功能介绍
0 介绍EtherCAT主站SOEM文件及主要功能函数 1. soem介绍:2 soem主要功能文件说明:3 soem下载链接4 编译soem4.1 Windows (Visual Studio):4.2 Linux & macOS: 该文档修改记录:总结 1. soem介绍: SOEM&…...
【Python机器学习】零基础掌握RFE特征选择
如何在数据分析中选出关键特征? 面对大量、高维度的数据,如何有效地选取关键特征以提高模型效率和准确度?这是数据分析领域中常见的问题。解决这个问题的一种方法就是递归特征消除(RFE)算法。 假设一个房地产公司希望预测房价,他们收集了很多关于房子的信息,如面积、房…...
R语言的极值统计学、分位数回归、机器学习方法
受到气候变化、温室效应以及人类活动等因素的影响,自然界中极端高温、极端环境污染、大洪水和大暴雨等现象的发生日益频繁;在人类社会中,股市崩溃、金融危机等极端情况也时有发生;今年的新冠疫情就是非常典型的极端现象。研究此类…...
【SpringCloudNetflix】一图理解Spring Cloud Netflix解决了那些微服务问题?
什么是微服务理解: SpringCloudNetflix解决的问题理解: SpringCloudNetflix核心点: 注册中心:Eureka负载均衡:Ribbon、Feign服务熔断:Hystrix服务降级:Hystrix服务监控:Hystrix Da…...
C++环境配置【学习笔记(一)】
文章目录 1、安装 VS Code 插件2、VS Code SSH远程连接Ubuntu主机3、编写py程序及 debug4、编写C程序5、C程序的 debug6、附录:vs code 中变量解释 C开发工具:Visual Studio Code 下载地址: 地址 其中本文将介绍使用 VS Code ssh 远程连接 a…...
Python数据结构——树
树(Tree)是一种重要的数据结构,它在计算机科学中被广泛应用,用于构建层次结构、组织数据和解决各种问题。本文将详细介绍Python中树数据结构的使用,包括二叉树、二叉搜索树、平衡二叉树等,并提供示例代码来…...
Simulink和GUI联合使用
1、内容简介 略 9-可以交流、咨询、答疑 2、内容说明 Simulink和GUI联合使用 Simulink、GUI、参数传递 3、仿真分析 4、参考论文 略...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...
边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...
echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式
pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图,如果边框加在dom上面,pdf-lib导出svg的时候并不会导出边框,所以只能在echarts图上面加边框 grid的边框是在图里…...
