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

个人可以做淘宝客网站吗/今日国际军事新闻头条

个人可以做淘宝客网站吗,今日国际军事新闻头条,网站建设课程设计总结,建站之星切换模板线上OJ: 一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid1417\ 核心思想 首先、本题中提到 “ 至少 要花多少金币改造机器人,能获得 至少 k分 ”。看到这样的话语,基本可以考虑要使用 二分答案。 那么,本题中…
线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1417\

核心思想

首先、本题中提到 “ 至少 要花多少金币改造机器人,能获得 至少 k分 ”。看到这样的话语,基本可以考虑要使用 二分答案
那么,本题中的 答案 是什么?就是: 在确定维修金币g的情况下,能获得的分数是否会> k
由于本题中的 格子在同一条直线上,且只能从左往右跳,所以 每一种答案 都可以使用 动态规划 来解决。
而且动态规划的 dp 方程也很好找,因为 当前格子的最高分 肯定是由 之前某个最高分的格子跳过来的,即:

d p [ i ] = m a x ( d p [ i ] , d p [ j ] + a [ i ] ) dp[i] = max(dp[i], dp[j] + a[i]) dp[i]=max(dp[i],dp[j]+a[i])

所以,我们从 i 号格子前面的第一个格子开始查找得分最高的格子。在这里需要注意的是:不是所有的 j 都需要查找。只有当 j 的跳跃区间 [d-g, d+g] 能够触达(或包含)i坐标 的时候,这个 j 才能用于更新dp[i]。
以下三个举例(及配图)便于理解j和i的关系

举例1: i 号格子位于坐标10,j 号格子位于坐标5(此时 j 的跳跃区间为 [2,4],也就是 j 能跳到的地方为[7,9]),所以此时 j 号格子无法触达 i,所以 j 号格子不需要用于更新dp[i]。
举例2: i 号格子位于坐标10,j 号格子位于坐标5(此时 j 的跳跃区间为 [2,6],也就是 j 能跳到的地方为[7,11]),所以此时 j 号格子可以触达 i,所以 j 号格子需要用于更新dp[i]。
举例3: i 号格子位于坐标10,j 号格子位于坐标5(此时 j 的跳跃区间为 [6,8],也就是 j 能跳到的地方为[11,13]),所以此时 j 号格子无法触达 i,所以 j 号格子不需要用于更新dp[i]。

在这里插入图片描述

综上所述,有效的 j 点应该满足
d − g < = x [ i ] − x [ j ] < = d + g d-g < = x[i] - x[j] < = d+g dg<=x[i]x[j]<=d+g
我们令左边界为 l = d - g,右边界为 r = d + g,则仅当 满足①和②式的 j 点 才参与dp[i]的运算

x [ i ] − x [ j ] > = l x[i] - x[j] > = l x[i]x[j]>=l; ①
$x[i] - x[j] < =r $; ②

题解代码:
解法一:二分答案 + 动态规划(仅80%分数)
#include <bits/stdc++.h>
#define ll long long
#define MAXN 500005using namespace std;int n, d, k;ll x[MAXN], s[MAXN], dp[MAXN];// 检查花费g个金币进行改造后,最高得分是否会超过 k
bool check(int g)
{// 计算在花费g金币下,机器人每次向右跳的距离边界[l, r] = [d-g, d+g]。注:左边界不能小于1 int l = max(1, d - g);  // 机器人每次能跳跃的最小距离 int r = d + g;			// 机器人每次能跳跃的最大距离memset(dp, 0xaf, sizeof(dp));  // 全部初始化为一个很小的数。dp[0] = 0; // 数据即分数都从第一个格子开始,所以第0个格子初始化为0分 for(int i = 1; i <= n; i ++){// 从i的前一个格子开始枚举j,直到j枚举到起点(如果i和j之间的距离已经超过弹跳上限r,则没必要继续j--了) for(int j = i - 1; (j >= 0) && (x[i] - x[j] <= r); j --){// 如果j号格子距离i号格子不能太近,至少要≥机器人弹跳的最小距离”,否则就j--,寻找更远的j if(x[i] - x[j] >= l){// i的最高得分应该是从前面能跳过来的格子j里得分最高的格子跳过来的dp[i] = max(dp[i], dp[j] + s[i]);	if(dp[i] >= k) return true;}            }}return false;
}int main()
{scanf("%d%d%d", &n, &d, &k);for(int i = 1; i <= n; i ++)scanf("%lld%lld", &x[i], &s[i]);// 由于x[i]的坐标范围可到 10^9,在极端情况下有可能前面全是负值,只有最后一个x[n]是正值,此时要搜索的答案g也会达到 10^9(即一步跳到最后一个正值)。所以二分答案时 r 应取到 x[n]。但如此一来,效率就变低了,只能拿到80%的分数int l = 0, r = x[n], mid, ans = -1;  while(l <= r){mid = (l + r) >> 1;if(check(mid)){ans = mid;r = mid - 1;}else l = mid + 1;}cout << ans << endl;return 0;
}

以上方法只能拿到80分,因为二分答案的右区间 r 取值为 x[n],数据过于庞大。

解法二、二分答案 + 动态规划 + 单调队列(100%)

由于 二分答案时的 r 取值为 x[n]过于庞大,所以此时考虑对 check 函数进行优化。由于 dp[i] 是之前的某个最大值 dp[j] 跳过来,所以可以考虑优先队列;同时由于 j 是有区间的,所以考虑优先队列的升级版–单调队列(单调队列适合在一个动态小区间中寻找极值

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500005using namespace std;int n, d, k;ll x[MAXN], s[MAXN], dp[MAXN];//检查花费g个金币进行改造后,最高得分是否会超过k
bool check(int g)
{// 计算在花费g金币下,机器人每次向右跳的距离边界[l, r] = [d-g, d+g]。注:左边界不能小于1 ll l = max(1, d - g);  // 机器人每次向右跳的最小距离 ll r = d + g;			// 机器人每次向右跳的最大距离memset(dp, 0xaf, sizeof(dp));dp[0] = 0; // 数据即分数都从第一个格子开始,所以第0个格子初始化为0分 ll j = 0;deque<int> q;for(int i = 1;i <= n;i ++){// 根据区间[l, r],剔除队尾的  while(x[i] - x[j] >= l)	// 根据i查找所有符合跳跃左边界的j {// 将队列中比 dp[j] 还小的直接移除 (由于按照单调队列存储,故从队尾判断)while( !q.empty() && dp[q.back()] < dp[j] )q.pop_back();q.push_back(j); // 把 j 放到单调队列的尾部,此时dp[j]是当前区间内最小的 j ++;}// 根据区间 [l, r],剔除队头的 while(!q.empty() && x[q.front()] + r < x[i]) // 如果最大的格子距离i太远,已经超过弹跳上限r q.pop_front();	// 则说对对头元素不在 [l,r] 内,弹出 if(!q.empty())	// 如果此时队列依然非空,则取队首的元素下标 q.front() 来做 dp dp[i] = dp[q.front()] + s[i];if(dp[i] >= k)return true;}return false;
}int main()
{scanf("%d%d%d", &n, &d, &k);for(int i = 1; i <= n; i ++)scanf("%lld%lld", &x[i], &s[i]);int l = 0, r = x[n], mid, ans = -1;while(l <= r){mid = (l + r) >> 1;if(check(mid)){ans = mid;r = mid - 1;}else l = mid + 1;}cout << ans << endl;return 0;
}

备注:这道题想 混分 有点 ,虽然参考输入样例2中给出了输出 -1 的场景(即:所有正的分数总和依然达不到目标分数k),但是实际的测试数据中并没有这种情况,所以这道题骗分骗不到。

相关文章:

2017NOIP普及组真题 4. 跳房子

线上OJ&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1417\ 核心思想 首先、本题中提到 “ 至少 要花多少金币改造机器人&#xff0c;能获得 至少 k分 ”。看到这样的话语&#xff0c;基本可以考虑要使用 二分答案。 那么&#xff0c;本题中…...

网络与 Internet因特网的基本概念

目录 网络Internet &#xff08;互联网或互连网&#xff09;Internet&#xff08;因特网&#xff09;待续、更新中 网络 指将分布在不同地理位置的、相同或不同类型的网络通过网络互连设备&#xff08;中继器、网桥、路由器或网关等&#xff09;相互连接&#xff0c;形成一个范…...

vue-router 中 router-link 与 a 标签的区别

文章目录 前言 a标签定义 router-link定义 总结 前言 vue-router 中 router-link 与 a 标签的区别 a标签定义 <a> 标签定义超链接&#xff0c;用于从一张页面链接到另一张页面。 从一张页面跳转到另一张页面&#xff0c;但从这里来说就违背了多视图的单页Web应用这个…...

MySQL基础知识——MySQL事务

事务背景 什么是事务&#xff1f; 一组由一个或多个数据库操作组成的操作组&#xff0c;能够原子的执行&#xff0c;且事务间相互独立&#xff1b; 简单来说&#xff0c;事务就是要保证一组数据库操作&#xff0c;要么全部成功&#xff0c;要么全部失败。 注&#xff1a;MyS…...

【架构方法论(一)】架构的定义与架构要解决的问题

文章目录 一. 架构定义与架构的作用1. 系统与子系统2. 模块与组件3. 框架与架构4. 重新定义架构&#xff1a;4R 架构 二、架构设计的真正目的-别掉入架构设计的误区1. 是为了解决软件复杂度2. 简单的复杂度分析案例 三. 案例思考 本文关键字 架构定义 架构与系统的关系从业务逻…...

基于springboot实现人口老龄化社区服务与管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现人口老龄化社区服务与管理系统演示 摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了人口老龄化社区服务与管理平台的开发全过程。通过分析人口老龄化社区服务与管理平台方面的不足&#xff…...

代码随想录算法训练营第三十七天| LeetCode 738.单调递增的数字、总结

一、LeetCode 738.单调递增的数字 题目链接/文章讲解/视频讲解&#xff1a;https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html 状态&#xff1a;已解决 1.思路 如何求得小于等于N的最大单调递增的整数&#xff1f;98&am…...

C++动态内存管理 解剖new/delete详细讲解(operator new,operator delete)

讨厌抄我作业和不让我抄作业的人 讨厌插队和不让我插队的人 讨厌用我东西和不让我用东西的人 讨厌借我钱和不借给我钱的人 讨厌开车加塞和不让我加塞的人 讨厌内卷和打扰我内卷的人 一、C中动态内存管理 1.new和delete操作内置类型 2.new和delete操作自定义类型 二、operat…...

python-re正则笔记0.2.0

1. 匹配linux文件路径 from re import match, search,findall str"sh refreshConfig.sh /opt/client/ccc.txt /opt/client/ccc.dfs 胜多负少的"patter1"\/.\.\w" print(findall(patter1, str))""" [/opt/client/ccc.txt /opt/client/ccc…...

.NET SignalR Redis实时Web应用

环境 Win10 VS2022 .NET8 Docker Redis 前言 什么是 SignalR&#xff1f; ASP.NET Core SignalR 是一个开放源代码库&#xff0c;可用于简化向应用添加实时 Web 功能。 实时 Web 功能使服务器端代码能够将内容推送到客户端。 适合 SignalR 的候选项&#xff1a; 需要从服…...

【热门话题】常见分类算法解析

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 常见分类算法解析1. 逻辑回归&#xff08;Logistic Regression&#xff09;2. 朴…...

有效利用MRP能为中小企业带来什么?

在离散制造企业&#xff0c;主流的生产模式主要为面向订单生产和面向库存生产&#xff08;又称为预测生产&#xff09;&#xff0c;在中小企业中&#xff0c;一般为面向订单生产&#xff0c;也有部分面向库存和面向订单混合的生产方式&#xff08;以面向订单为主&#xff0c;面…...

InternlM2

第一次作业 基础作业 进阶作业 1. hugging face下载 2. 部署 首先&#xff0c;从github上git clone仓库 https://github.com/InternLM/InternLM-XComposer.git然后里面的指引安装环境...

2024-12.python高级语法

异常处理 首先我们要理解什么叫做**"异常”**&#xff1f; 在程序运行过程中&#xff0c;总会遇到各种各样的问题和错误。有些错误是我们编写代码时自己造成的&#xff1a; 比如语法错误、调用错误&#xff0c;甚至逻辑错误。 还有一些错误&#xff0c;则是不可预料的错误…...

【C语言】贪吃蛇项目(1) - 部分Win32 API详解 及 贪吃蛇项目思路

文章目录 一、贪吃蛇项目需要实现的基本功能二、Win32 API介绍2.1 控制台2.2 部分控制台命令及调用函数mode 和 title 命令COORD 命令GetStdHandle&#xff08;获取数据&#xff09;GetConsoleCursorInfo&#xff08;获取光标数据&#xff09;SetConsoleCursorInfo &#xff08…...

秋叶Stable diffusion的创世工具安装-带安装包链接

来自B站up秋葉aaaki&#xff0c;近期发布了Stable Diffusion整合包v4.7版本&#xff0c;一键在本地部署Stable Diffusion&#xff01;&#xff01; 适用于零基础想要使用AI绘画的小伙伴~本整合包支持SDXL&#xff0c;预装多种必须模型。无需安装git、python、cuda等任何内容&am…...

华为ensp中aaa(3a)实现telnet远程连接认证配置命令

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月14日18点49分 AAA认证的全称是Authentication、Authorization、Accounting&#xff0c;中文意思是认证、授权、计费。 以下是详细解释 认证&#xff08;Authentic…...

前端网络---http协议和https协议的区别

http协议和https的区别 1、http是超文本传输协议&#xff0c;信息是明文传输&#xff0c;https则是具有安全性的ssl加密传输协议。 2、http和https使用的端口不一样&#xff0c;http是80&#xff0c;https是443。 3、http的连接很简单&#xff0c;是无状态的&#xff08;可以…...

FactoryMethod工厂方法模式详解

目录 模式定义实现方式简单工厂工厂方法主要优点 应用场景源码中的应用 模式定义 定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。 Factory Method 使得一个类的实例化延迟到子类。 实现方式 简单工厂 以下示例非设计模式&#xff0c;仅为编码的一种规…...

Java基础-知识点1(面试|学习)

Java基础-知识点1 Java与C、PythonJava &#xff1a;C&#xff1a;Python: java 与 C的异同相似之处&#xff1a;区别&#xff1a; Java8的新特性Lambda 表达式&#xff1a;Stream API&#xff1a;接口的默认方法和静态方法&#xff1a; 基本数据类型包装类自动装箱与自动拆箱自…...

【InternLM 实战营第二期-笔记1】书生浦语大模型开源体系详细介绍InternLM2技术报告解读(附相关论文)

书生浦语是上海人工智能实验室和商汤科技联合研发的一款大模型,很高兴能参与本次第二期训练营&#xff0c;我也将会通过笔记博客的方式记录学习的过程与遇到的问题&#xff0c;并为代码添加注释&#xff0c;希望可以帮助到你们。 记得点赞哟(๑ゝω╹๑) 书生浦语大模型开源体系…...

【免费】基于SOE算法的多时段随机配电网重构方法

1 主要内容 该程序是完全复现《Switch Opening and Exchange Method for Stochastic Distribution Network Reconfiguration》&#xff0c;也是一个开源代码&#xff0c;网上有些人卖的还挺贵&#xff0c;本次免费分享给大家&#xff0c;代码主要做的是一个通过配电网重构获取…...

Swift面向对象编程

类的定义与实例化&#xff1a; Swift中定义一个类使用class关键字&#xff0c;类的属性和方法都写在大括号内。示例代码如下&#xff1a; class MyClass {var property1: Intvar property2: Stringinit(property1: Int, property2: String) {self.property1 property1self.pr…...

IEDA 的各种常用插件汇总

目录 IEDA 的各种常用插件汇总1、 Alibaba Java Coding Guidelines2、Translation3、Rainbow Brackets4、MyBatisX5、MyBatis Log Free6、Lombok7、Gitee IEDA 的各种常用插件汇总 1、 Alibaba Java Coding Guidelines 作用&#xff1a;阿里巴巴代码规范检查插件&#xff0c;…...

浅谈C语言中异或运算符的10种妙用

目录 1、前言 2、基本准则定律 3、妙用归纳 4、总结 1、前言 C语言中异或运算符^作为一个基本的逻辑运算符&#xff0c;相信大家都知道其概念&#xff1a;通过对两个相同长度的二进制数进行逐位比较&#xff0c;若对应位的值不同&#xff0c;结果为 1, 否则结果为 0。 但是…...

Canal--->准备MySql主数据库---->安装canal

一、安装主数据库 1.在服务器新建文件夹 mysql/data&#xff0c;新建文件 mysql/conf.d/my.cnf 其中my.cnf 内容如下 [mysqld] log_timestampsSYSTEM default-time-zone8:00 server-id1 log-binmysql-bin binlog-do-db mall # 要监听的库 binlog_formatROW2.启动数据库 do…...

vs配置opencv运行时“发生生成错误,是否继续并运行上次的成功生成”BUG解决办法

vs“发生生成错误&#xff0c;是否继续并运行上次的成功生成” 新手在用vs配置opencv时遇到这个错误时&#xff0c;容易无从下手解决。博主亲身经历很有可能是release/debug模式和配置文件不符的问题。 在配置【链接器】→【输入】→【附加依赖项】环节&#xff0c;编辑查看选择…...

Dryad Girl Fawnia

一个可爱的Dryad Girl Fawnia的三维模型。她有ARKit混合形状,人形装备,多种颜色可供选择。她将是一个完美的角色,幻想或装扮游戏。 🔥 Dryad Girl | Fawnia 一个可爱的Dryad Girl Fawnia的三维模型。她有ARKit混合形状,人形装备,多种颜色可供选择。她将是一个完美的角色…...

内存相关知识(新)

基本概念 内存层次结构&#xff1a;内存层次结构是一种层次化的存储设备结构&#xff0c;它包括寄存器、缓存、主存和辅助存储器。每一层次的存储设备都有不同的速度、容量和成本。 内存单元&#xff1a;内存被划分为一系列连续的内存单元&#xff0c;每个单元都有一个唯一的地…...

C++从入门到精通——static成员

static成员 前言一、static成员概念例题 二、 static成员的特性特性例题静态成员函数可以调用非静态成员函数吗非静态成员函数可以调用类的静态成员函数吗 前言 一、static成员 概念 声明为static的类成员称为类的静态成员&#xff0c;用static修饰的成员变量&#xff0c;称之…...