第七讲---贪心(上课)

1.股票买卖


一、贪心


考虑一种方案,在每次上升的前一天购入股票,并在上升后的当天卖出的方案
if (w[i] > w[i - 1])res += w[i] - w[i - 1];
接下来证明该贪心思路得出的方案即是最优解。
(1)证明贪心解 ≥ 最优解:
由于贪心解都是取区间长度为 1 的解,因此假设存在于最优解中的某个区间 [i,j] 的长度 >1
那么会出现一下三种情况:

对应三种情形:最优解选取的区间最终点位于上方、下方、相等。
对于情形一:显然 最优解 < 贪心解
对于情形二:显然 最优解 <贪心解
对于情形三:毫无疑问,这就是存在于贪心解中的情形,因此 贪心解 = 最优解
得证
(2)证明贪心解 ≤最优解:
这部分无需证明,因为贪心解即是合法解,所以他的方案必定大于等于最优解
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int w[N];int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);int res = 0;for (int i = 2; i <= n + 1; ++i) {if (w[i] - w[i - 1] > 0) res += w[i] - w[i - 1];}printf("%d\n", res);return 0;
}
二、闫氏DP分析法

具体的状态机模型分析如下图:

一共只2有种状态:
1. 当前处于未持股状态0:
对应可以进行的转换:
0->0 (不买入,继续观望,那么就什么都不发生)
0->1 (买入股票,那么收益就要减去当前市场的股票价格)
2. 当前处于持股状态1:
对应可以进行的转换:
1->1 (不卖出,继续观望,那么就什么都不发生)
1->0 (卖出股票,那么收益就要加上当前市场的股票价格)
#include <iostream>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][2];int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);f[0][1] = -INF;for (int i = 1; i <= n; ++i) {f[i][0] = max(f[i - 1][0], f[i - 1][1] + w[i]);f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);}printf("%d\n", f[n][0]);return 0;
}
2.货舱选址



#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main () {scanf ("%d",&n);for (int i = 1;i <= n;i++) scanf ("%d",&a[i]);sort (a + 1,a + 1 + n);int ans = 0;for (int i = 1,j = n;i <= j;i++,j--) ans += a[j] - a[i];printf ("%d\n",ans);return 0;
}
3.糖果传递



相关文章:
第七讲---贪心(上课)
1.股票买卖 一、贪心 考虑一种方案,在每次上升的前一天购入股票,并在上升后的当天卖出的方案 if (w[i] > w[i - 1])res w[i] - w[i - 1];接下来证明该贪心思路得出的方案即是最优解。 (1)证明贪心解 ≥ 最优解: …...
计算机如何思考与图灵完备
图灵完备是针对一套数据操作规则而言的概念,数据操作规则可以是一门编程语言,也可以是计算机实现里面的指令集,比如C/C++是图图灵完备的,通用CPU也是图灵完备的,但是GPU却不一定是图灵完备的。说白了图灵完备定义了一套规则,当这套规则可以实现图灵迹模型里的全部功能时,…...
惠普LaserJet M1005 MFP报错b2
故障现象: 惠普LaserJet M1005 MFP开机后直接报b2错误; 检测维修: 故障大意是:机器的硬件可能出现点突变,此问题建议联系当地维修中心进行处理。...
网络协议(TCP/IP)
目录一、网络分层模型二、OSI模型三、网络传输原理四、TCP/IP1、TCP/IP 原理2、TCP 三次握手/四次挥手3、Http协议和TCP/IP的区别五、HTTP原理六、HTTPS原理七、CDN原理一、网络分层模型 互联网的本质就是一系列的网络协议,最早由ISO国际组织定义为7层网络参考模型…...
2023河南省第二届职业技能大赛郑州市选拔赛“网络安全” 项目比赛样题任务书
2023河南省第二届职业技能大赛郑州市选拔赛“网络安全” 项目比赛样题任务书2023河南省第二届职业技能大赛郑州市选拔赛“网络安全” 项目比赛样题任务书A模块基础设施设置/安全加固(200分)A-1:登录安全加固(Windows, Linux&#…...
6、流程控制
目录一、if二、switch三、for四、break与continue五、goto与Label一、if if使用:逻辑表达式成立,就会执行{}里的内容;逻辑表达式不需要加() if 5 > 9 {fmt.Println("5>9") }if句子中允许包含1个(仅1个)分号:在分…...
Linux中最基本常见命令总结
❤❤💛💛💚💚💙💙💜💜您的认可是对我最大的帮助💜💜💙💙💚💚💛💛❤❤ 🤎&…...
Python学习-----模块2.0(常用模块之时间模块-->time)
目录 前言: time简介 导入模块 1.时间戳 2.时间元组 (1)把时间戳转换为元组形式 (2)元组转换为时间戳输出 (3)把元组转换为格式化时间 (4)把时间戳转换为格式化时间…...
XXL-JOB分布式任务调度框架(二)-策略详解
文章目录1.引言2.任务详解2.1.执行器2.2.基础配置3.路由策略(第一个)-案例4.路由策略(最后一个)-案例5.轮询策略-案例6.随机选取7.轮询选取8.一致性hash9.最不经常使用 (LFU)10.最近最久未使用(LRU)11.故障转移12.忙碌转移13.分片广播任务14.父子任务15.…...
JAVA练习54-最小栈
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、题目-最小栈 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 前言 提示:这里可以添加本文要记录的大概内容: 2月18日练习内容…...
Redis-哨兵模式以及集群
在开始这部分内容之前需要先说一下复制功能,因为这是Redis实现主从数据同步的实现方式。复制功能如果存在两台服务器的话,我们可以使用redis的复制功能,让一台服务器去同步另一台服务器的数据。现在我启动了两台redis服务器,一个端…...
过滤器和监听器
1、过滤器Filter 作用是防止SQL注入、参数过滤、防止页面攻击、空参数矫正、Token校验、Session验证、点击率统计等等; 使用Filter的步骤 新建类,实现Filter抽象类;重写init、doFilter、destroy方法;在SpringBoot入口中添加注解…...
Acwing 第 91 场周赛
Powered by:NEFU AB-IN B站直播录像! Link 文章目录Acwing 第 91 场周赛A AcWing 4861. 构造数列题意思路代码B AcWing 4862. 浇花题意思路代码C AcWing 4863. 构造新矩阵题意思路代码Acwing 第 91 场周赛 A AcWing 4861. 构造数列 题意 略 思路 将每个数的每一位…...
JavaEE|套接字编程之UDP数据报
文章目录一、DatagramSocket API构造方法常用方法二、DatagramPacket API构造方法常用方法E1:回显服务器的实现E2:带有业务逻辑的请求发送一、DatagramSocket API 在操作系统中,把socket对象当成了一个文件处理。等价于是文件描述符表上的一项。 普通的文件…...
如何使用Python创建一个自定义视频播放器
目录 1、安装vlc的64位版本。 2、安装python的vlc模块。 3、编写如下代码,包含了播放,暂停,停止、音量控制功能。 4、来看一看运行结果。 5、如果遇到播放不了的问题,解决方式如下: 这个例子使用VLC作为视频播放器…...
Elasticsearch进行优化-使用索引拆分(Split)和索引收缩(shrink )
一、索引拆分和收缩的场景 在Elasticsearch集群部署的初期我们可能评估不到位,导致分配的主分片数量太少,单分片的数据量太大,导致搜索时性能下降,这时我们可以使用Elasticsearch提供的Split功能对当前的分片进行拆分,…...
数论 —— 高斯记号(Gauss mark)
定义 数学上,高斯记号(Gauss mark)是指对取整符号和取小符号的统称,用于数论等领域。 设 x∈Rx \in \textbf{R}x∈R,用 [x][x][x] 表示不超过 xxx 的最大整数。也可记作 [x][x][x]。设 x∈Rx \in \textbf{R}x∈R&…...
【随笔】程序员眼中的 CPU,“没有灵魂的躯体”
引言 先引用一段比较有意思的论述: 现实中每个人是由两部分构成,灵魂和躯体,灵魂依附于躯体游走于世间,现实中我们面对的每个人其实面对的是其灵魂而非肉体,肉体不过是表象而已。 灵魂本性乃一恶物,寄生于…...
算法的时间复杂度
算法在编写成可执行程序后,运行时需要消耗时间资源和空间(内存)资源,因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的。 时间复杂度主要衡量一个算法运行的快慢,而空间复杂度主要衡量一个算法运…...
华为OD机试 - 叠放书籍(Python) | 机试题算法思路 【2023】
最近更新的博客 华为OD机试 - 寻找路径 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 五键键盘 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - IPv4 地址转换成整数 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 对称美学 | 备考思路,刷题要点,答疑 …...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
