当前位置: 首页 > news >正文

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 饥饿的奶牛

根据题意可以知道是一个动态规划&#xff0c;看完数据范围之后可以知道是一个线性DP。 解决方法有点类似于背包问题&#xff0c;枚举背包的每一个空间。 如果把坐标轴上每个点都看成一个块儿&#xff0c;只需要按顺序求出前 i 个块儿的最大牧草堆数&#xff0c;f[i] 就是前i的…...

【软考系统架构设计师】2021年系统架构师综合知识真题及解析

本文主要分享2021年下半年系统架构师综合知识历年真题以及本人在做题时的所思所想。题目序号有点混乱&#xff0c;可忽略 【01】.某计算机系统页面大小为4K&#xff0c;进程P1的页面变换表如下图所示&#xff0c;看P1要访问数据的逻辑地址为十六进制1B1AH,那么该逻辑地址经过变…...

如何在忘记手机密码或图案时重置 Android 手机?

忘记手机密码或图案是 Android 用户一生中不得不面对的最令人沮丧的事情之一。恢复 Android 设备的唯一方法是在 Android 设备上恢复出厂设置。但许多用户不使用此方法&#xff0c;因为此过程会擦除您设备上可用的所有个人数据。 但是&#xff0c;有一种方法可以在不丢失任何数…...

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&#xff1a;https://arxiv.org/abs/1910.01108 Train Loss: DistilBERT&#xff1a; DistilBERT具有与BERT相同的一般结构&#xff0c;层数减少2倍&#xff0c;移除token类型嵌入和pooler。从老师那里取一层来初始化学生。 The token-type embeddings and the pooler a…...

202212 青少年等级考试机器人实操真题三级

202212 青少年等级考试机器人实操真题三级 考试时间&#xff1a;60分钟 总分&#xff1a;100 及格分&#xff1a;60 一、问答题 (共1题&#xff0c;每题100分) 1、实际操作(共1题&#xff0c;共100分) 请考生在实操考试结束前将本题作答程序文件按“说明”要求完成上传。 1. 主…...

token正确不报错,token失效后却出现报跨域错误

1.今天在使用koajs开发项目时&#xff0c;突然发现前端配置axios的response获取不到后端定义的token失效内容了&#xff0c;取而代之的是出现了跨域的错误。 2. 我马上去查找koajs的跨域中间件配置&#xff0c;发现配置完好cors&#xff0c;token正确时&#xff0c;接口正常访问…...

STM32中除零运算,为何程序不崩溃?

在 C 语言中&#xff0c;除零运算会导致异常吗&#xff1f; 在 C 语言中&#xff0c;当一个数除以零时&#xff0c;会导致除法运算错误&#xff0c;通常表现为“除以零”错误或被称为“浮点异常”&#xff08;floating-point exception&#xff09;。 对于整数除法&#xff0c…...

sprinbboot 2.7启动不生成日志文件

新增了一个springboot项目&#xff0c;通过idea 调试&#xff0c;并且在idea 的vm options中指定-Dlogging.configclasspath:logback-pro.xml 或者 -Dlogging.configclasspath:logback-dev.xml 都能正常生成对应的日志文件。 部署到测试环境以及生产环境&#xff0c;日志文件却…...

Kafka - 3.x 图解Broker总体工作流程

文章目录 Zk中存储的kafka的信息Kafka Broker总体工作流程1. broker启动后向zk中注册2. Controller谁先启动注册&#xff0c;谁说了算3. 由选举出来的Controller监听brokers节点的变化4. Controller决定leader选举5. Controller将节点信息上传到Zk中6. 其他Controller从zk中同步…...

APP自动化测试 ---- Appium介绍及运行原理

在面试APP自动化时&#xff0c;有的面试官可能会问Appium的运行原理&#xff0c;以下介绍Appium运行原理。 一、Appium介绍 1.Appium概念 Appium是一个开源测试自动化框架&#xff0c;可用于原生&#xff0c;混合和移动Web应用程序测试。它使用WebDriver协议驱动IOS&#xf…...

学习模板发布

学习目标&#xff1a; 提示&#xff1a;这里可以添加学习目标 例如&#xff1a; 一周掌握 Java 入门知识 学习内容&#xff1a; 提示&#xff1a;这里可以添加要学的内容 例如&#xff1a; 搭建 Java 开发环境掌握 Java 基本语法掌握条件语句掌握循环语句 学习时间&#x…...

Hive 视图和索引

1.视图 1.1 简介 Hive 中的视图和 RDBMS 中视图的概念一致,都是一组数据的逻辑表示,本质上就是一条 SELECT 语句的结果集。视图是纯粹的逻辑对象,没有关联的存储 (Hive 3.0.0 引入的物化视图除外),当查询引用视图时,Hive 可以将视图的定义与查询结合起来,例如将查询中的过…...

EtherCAT主站SOEM-- 0 SOEM下载编译及文件功能介绍

0 介绍EtherCAT主站SOEM文件及主要功能函数 1. soem介绍&#xff1a;2 soem主要功能文件说明&#xff1a;3 soem下载链接4 编译soem4.1 Windows (Visual Studio)&#xff1a;4.2 Linux & macOS&#xff1a; 该文档修改记录&#xff1a;总结 1. soem介绍&#xff1a; SOEM&…...

【Python机器学习】零基础掌握RFE特征选择

如何在数据分析中选出关键特征? 面对大量、高维度的数据,如何有效地选取关键特征以提高模型效率和准确度?这是数据分析领域中常见的问题。解决这个问题的一种方法就是递归特征消除(RFE)算法。 假设一个房地产公司希望预测房价,他们收集了很多关于房子的信息,如面积、房…...

R语言的极值统计学、分位数回归、机器学习方法

受到气候变化、温室效应以及人类活动等因素的影响&#xff0c;自然界中极端高温、极端环境污染、大洪水和大暴雨等现象的发生日益频繁&#xff1b;在人类社会中&#xff0c;股市崩溃、金融危机等极端情况也时有发生&#xff1b;今年的新冠疫情就是非常典型的极端现象。研究此类…...

【SpringCloudNetflix】一图理解Spring Cloud Netflix解决了那些微服务问题?

什么是微服务理解&#xff1a; SpringCloudNetflix解决的问题理解&#xff1a; SpringCloudNetflix核心点&#xff1a; 注册中心&#xff1a;Eureka负载均衡&#xff1a;Ribbon、Feign服务熔断&#xff1a;Hystrix服务降级&#xff1a;Hystrix服务监控&#xff1a;Hystrix Da…...

C++环境配置【学习笔记(一)】

文章目录 1、安装 VS Code 插件2、VS Code SSH远程连接Ubuntu主机3、编写py程序及 debug4、编写C程序5、C程序的 debug6、附录&#xff1a;vs code 中变量解释 C开发工具&#xff1a;Visual Studio Code 下载地址&#xff1a; 地址 其中本文将介绍使用 VS Code ssh 远程连接 a…...

Python数据结构——树

树&#xff08;Tree&#xff09;是一种重要的数据结构&#xff0c;它在计算机科学中被广泛应用&#xff0c;用于构建层次结构、组织数据和解决各种问题。本文将详细介绍Python中树数据结构的使用&#xff0c;包括二叉树、二叉搜索树、平衡二叉树等&#xff0c;并提供示例代码来…...

Simulink和GUI联合使用

1、内容简介 略 9-可以交流、咨询、答疑 2、内容说明 Simulink和GUI联合使用 Simulink、GUI、参数传递 3、仿真分析 4、参考论文 略...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...