当前位置: 首页 > 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、参考论文 略...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...