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

DP之书架

news 来源：原创 2025/6/17 16:01:48

现按一定顺序给出所有要放置于书架上的书，共有 n 本，第 i 本书有一个长度 hi。

书架有若干层，层与层之间的宽度不一定相等，但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时，每层上的书的长度之和不能超过一个给定的参数 m，且任何层上的书必须是给出的书的序列中连续的几本。

书架的宽度是所有层的宽度之和，求书架的最小宽度。

输入格式

输入的第一行包含两个整数 n 和 m。

第 2 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数代表第 i 本书的长度 hi。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

输出 #1复制

5思路：

设dp[i]表示1~i放到书架上的最小代价，

则dp[i]=min{0<j<=i&&sum[i]-sum[j-1]<=m | max{j<=k<=i|height[k]}+dp[j-1]} 显然这个dp是O(n^2)的，一定会超时，于是思考优化。

考虑数据结构：需要能直接读出dp[i]的值，但是由于最大值会随时变动，我们要想办法维护最大值。

注意到每个数字只会对它前面的值的最大值造成影响，于是可以使用单调栈统计每个数最左端可以延伸到哪里，也就是说最多能到哪里使得所有数字都不大于它。

有了单调栈预处理出的延伸值，我们可以使用线段树维护dp。

假设当前计算到i，则每个叶子节点j表示max{j<k<=i|height[k]+dp[j]}，考虑如何更新。

更新有两种，一种是更新叶子节点的dp值，一种是把区间[a,b]的最大值更新为t，也就是把[a,b]全部置为t。

于是，每个节点维护三个值：

1.lazy，标记[a,b]置为t的操作

2.res，如果是叶子节点就是max{j<k<=i|height[k]+dp[j]}，否则就表示所有儿子节点中上述值最小的那个

3.mn，如果是叶子节点就表示叶子节点对应的dp值，否则就表示所有儿子节点中dp值的最小值

于是线段树就可以投入使用了，

对于第一种更新，直接自下而上更新一遍mn值即可；

对于第二种更新，自上而下pushdown，根据dp的递推公式可知res[i]=mn[i]+lazy[i]。

具体如何操作呢？

单调栈预处理之后，由于有dp[0]=0，因此update1(0,0)（表示在0位置将dp值设为0）

然后对于每个i，记单调栈延伸值为k，满足sum[i]-sum[j]<=m的最小的j记为a，

首先update2(k,i,height[i])（表示将区间[k,i)的最大值置为height[i]，注意区间左闭右开！）

然后直接dp[i]=query(a,i)（表示查询区间[a,i)中res的最小值）

最后再update1(i,dp[i])，也就是把i位置的dp值设置一遍。

综上所述，单调栈预处理O(n)，线段树O(nlogn)，因此总复杂度O(nlogn)
代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 100005, maxt = 262144;
int dp[maxn], high[maxn], sta[maxn], sum[maxn], n, m;
int lazy[maxt], mn[maxt], res[maxt], tn;
inline void pushup(int x){int ls = x * 2 + 1, rs = x * 2 + 2;mn[x] = min(mn[ls], mn[rs]);if(lazy[x] != 0) res[x] = mn[x] + lazy[x];else res[x] = min(res[ls], res[rs]);
}
inline void pushdown(int x){if(!lazy[x]) return;int ls = x * 2 + 1, rs = x * 2 + 2;lazy[ls] = lazy[rs] = lazy[x]; lazy[x] = 0;res[ls] = lazy[ls] + mn[ls];res[rs] = lazy[rs] + mn[rs];
}
void update1(int x, int s){x += tn - 1;mn[x] = s;while(x > 0){x = (x - 1) / 2;mn[x] = min(mn[x], s);}
}
void update2(int a, int b, int x, int l = 0, int r = tn, int k = 0){if(a >= r || b <= l) return;if(a <= l && b >= r){lazy[k] = x;res[k] = x + mn[k];return;}pushdown(k);update2(a, b, x, l, (l + r) / 2, k * 2 + 1);update2(a, b, x, (l + r) / 2, r, k * 2 + 2);pushup(k);
}
int query(int a, int b, int l = 0, int r = tn, int k = 0){if(a >= r || b <= l) return INF;if(a <= l && b >= r) return res[k];pushdown(k);return min(query(a, b, l, (l + r) / 2, k * 2 + 1),query(a, b, (l + r) / 2, r, k * 2 + 2));
}
int main(){scanf("%d%d", &n, &m);for(tn = 1; tn <= n; tn <<= 1);memset(mn, 0x3f, sizeof(mn));memset(res, 0x3f, sizeof(res));update1(0, 0);for(int i = 1, tp = 0, j = 0; i <= n; i++){scanf("%d", high + i);sum[i] = high[i] + sum[i - 1];while(tp > 0 && high[sta[tp - 1]] <= high[i]) tp--;while(sum[i] - sum[j] > m) j++;int lm = max(j, !tp ? 0 : sta[tp - 1]);sta[tp++] = i;update2(lm, i, high[i]);dp[i] = query(j, i);update1(i, dp[i]);}printf("%d", dp[n]);return 0;
}

AC截图：

DP之书架

现按一定顺序给出所有要放置于书架上的书，共有 n 本，第 i 本书有一个长度 hi。书架有若干层，层与层之间的宽度不一定相等，但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时，每层上的书的长度之和不能超过…...

编程日记 2025/6/2 20:03:29

Python Cookbook-6.11 缓存环的实现

任务你想定义一个固定尺寸的缓存，当它被填满时，新加入的元素会覆盖第一个(最老的)元素。这种数据结构在存储日志和历史信息时非常有用。解决方案当缓存填满时，本节解决方案及时地修改了缓存对象，使其从未填满的缓存类变成了…...

编程日记 2025/6/3 22:11:46

计算机网络基本概念

层次名称主要功能第七层应用层直接面向用户，提供应用服务（如浏览网页、发邮件）第六层表示层处理数据格式、加密解密、压缩解压第五层会话层建立、管理、终止会话（连接）第四层传输层提供端到端的数据传输（如…...

编程日记 2025/5/31 10:20:09

Eigen线性代数求解器（分解类）

1. 核心分解类概览 Eigen 提供多种矩阵分解方法，适用于不同矩阵类型（稠密/稀疏、正定/非正定等）： 分解类适用矩阵类型分解形式典型应用场景PartialPivLU方阵（可逆）APLUAPLU通用线性方程组求解FullPivLU任…...

编程日记 2025/6/1 19:27:23

【Android】四大组件之Service

目录一、什么是Service 二、启停 Service 三、绑定 Service 四、前台服务五、远程服务扩展六、服务保活七、服务启动方法混用你可以把Service想象成一个“后台默默打工的工人”。它没有UI界面，默默地在后台干活，比如播放音乐、下载文件、处理…...

编程日记 2025/6/1 6:10:42

VO包装类和实体类分别是什么？区别是什么？

VO包装类和实体类 1. 实体类（Entity Class）是什么？2. VO包装类（Value Object Class）是什么？3. VO包装类和实体类的区别4. 实际应用中的区别5. 举例5.1. 实体类（Entity Class）的定义与…...

编程日记 2025/5/30 20:32:09

如何创建一个C#项目(基于VS2022版)

一.先找到要保存项目的位置,新建一个文件夹二.打开VisualStudio,选择创建新项目三.选择模版: 选择操作语言和操作系统这个是跨平台的初学在windows系统上,可选择其他,下面这个是不带窗体模版也可根据需要选择带窗体模版点击下一步填写项目名称,选择项目保存位置,填写解…...

编程日记 2025/6/3 13:56:47

RabbitMQ 四种交换机（Direct、Topic、Fanout、Headers）详解

本文是博主在梳理 RabbitMQ 知识的过程中，将所遇到和可能会遇到的基础知识记录下来，用作梳理 RabbitMQ 的整体架构和功能的线索文章，通过查找对应的知识能够快速的了解对应的知识而解决相应的问题。文章目录一、直连交换机（Dire…...

编程日记 2025/5/29 22:19:19

聚合分销系统开发：短剧小说外卖网盘电商cpscpa系统

聚合分销系统是一种整合了多种分销项目和功能的综合性平台，其核心在于通过CPS（按销售付费）和CPA（按行为付费）两种模式，为推广者提供多样化的赚钱机会。以下是聚合分销系统的主要项目和功能： 一…...

编程日记 2025/6/4 11:35:51

【Flume 】Windows安装步骤、配置环境

🛠 Flume 是什么？ Apache Flume 是一个高效、可靠、可扩展的数据收集系统，通常用于收集日志、流数据，比如收集数据到 HDFS、Kafka 等。虽然 Flume 本身是为 Linux 服务器设计的，但在 Windows 本地也是能跑起来的&a…...

编程日记 2025/6/4 7:23:44

【信息系统项目管理师】高分论文：论质量管理和进度管理（智慧旅游平台建设项目）

更多内容请见：备考信息系统项目管理师-专栏介绍和目录文章目录论文1、规划质量管理2、质量保证3、质量控制论文 2019年3月，我作为项目经理,参加了某市智慧旅游平台建设项目，负责项目的全面管理，该项目以打造一流的国内外生态旅游城市为目标，旨在大数据云平台建设的基…...

编程日记 2025/6/3 10:40:50

一致性哈希详解：优雅地扩展分布式系统

引言对于哈希算法，相信大家一定不会陌生。它经常被用在负载均衡、分库分表等场景中。例如，在进行分库分表时，我们可能初步根据业务分析，确定 128 张表足以满足当前的数据量需求。此时，当需要插入或查询一条记录时&am…...

编程日记 2025/6/1 10:39:44

pytest 技术总结

目录一 pytest的安装： 二 pytest有三种启动方式： 三用例规则： 四配置框架： 一 pytest的安装： pip install pytest # 安装 pip install pytest -U # 升级到最新版二 pytest有三种启动方式： 1…...

编程日记 2025/6/1 6:00:27

数据库MySQL学习——day5（总结与复习实践）

文章目录 1、复习总结1.1. 数据库基础1.2. 表操作1.3. 数据操作1.4. 更新与删除 2、实践任务：创建学生管理系统数据库2.1. 数据库设计2.2. 创建表的SQL语句2.3. 插入示例数据2.4. 查询与数据操作示例 3、调试与练习4、今日小结 1、复习总结 1.1. 数据库基础数据…...

编程日记 2025/6/2 4:34:23

unity bug

发现一个奇怪的bug，就是某些unity版本打包apk时候不允许StreamingAssets里面有中文文件或者中文路径。比如下图这面这俩都是不行的。解决方案：中文改为英文即可。一般报错信息如下： > Configure project :launcher WARNING:The option s…...

编程日记 2025/5/25 2:12:15

苹果计划2026年底前实现美版iPhone“印度造”，以减轻关税及地缘政治风险

基于 6 个来源据多家媒体报道，苹果公司计划在2026年底前，实现在印度组装销往美国的大部分或全部iPhone手机，以减轻关税和地缘政治紧张局势带来的风险。这一目标意味着苹果需将印度的iPhone产量增加一倍以上，凸显其供应链多元化战…...

编程日记 2025/5/30 20:12:40

新增Webhook通知功能，文档目录树展示性能优化，zyplayer-doc 2.5.1 发布啦！

zyplayer-doc是一款适合企业和个人使用的WIKI知识库管理工具，支持在线编辑富文本、Markdown、表格、Office文档、API接口、思维导图、Drawio以及任意的文本文件，支持基于知识库的AI问答，专为私有化部署而设计，最大程度上保证企业或…...

编程日记 2025/6/2 15:31:17

【量化交易笔记】17.多因子的线性回归模型策略

前言上一篇介绍了因子的评价和分析方法，让我知道如何判断该因子的作用，以及对最终结果的影响，其最大的问题，他只能评价和分析单因子，而对多个因子，不能直接加以评价。我们自然会想到，如果是多…...

编程日记 2025/6/4 17:51:29

五年经验Java开发如何破局创业

🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息文章目录五年经验Java开发如何破局创业一、创业方向筛选与优劣势分析**方向1：技术教育/在线课程开发****方向2：企业级技术服务外包****方向3：技…...

编程日记 2025/5/29 2:38:41

定制一款国密浏览器(11)：SM2算法的椭圆曲线参数定义

在国密算法中，SM2 算法是最复杂的，不仅是算法本身比较复杂，其应用场景也复杂。不管 SM2 算法本身有多复杂，作为开发者，我们需要知道的是 SM2 算法是建立在椭圆曲线算法（ECC）之上。关于 SM2 算法和椭圆曲线算法之间的关系，参考我之前的一篇文章：解读国密非对称加密算…...

编程日记 2025/5/30 22:32:45

RAG技术与应用---0426

大语言模型>3.10 课程中会用到python 工具箱： faiss,modelscope,langchain,langchain_community，PyPDF2 1）大模型应用开发的三种模式提示词没多少工作量，微调又花费时间费用，RAG是很多公司招聘用来对LLM进行应用…...

编程日记 2025/6/3 2:06:05

STM32的开发环境介绍

目录 STM32软件环境 Keil软件在线安装其他软件环境安装 STM32开发的几种方式 STM32寄存器版本和库函数版本标准外设库的作用： STM32软件环境 STM32 的集成开发环境（IDE）：编辑编译软件常见的环境： (1)KEIL&a…...

编程日记 2025/6/1 11:41:03

【生成式AI】从原理到实践的创造性革命

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心代码实现（文生图） 三、性能对比测试方法论量化数据对比结果分析四、最佳实践推荐方…...

编程日记 2025/6/4 17:51:38

Win下Pycharm运行/调试配置脚本形参执行替换Linux下终端执行，进行调试需要注意的

Linux下终端执行 python demo/image_demo.py demo/demo.jpg rtmdet_tiny_8xb32-300e_coco.py --weights rtmdet_tiny_8xb32-300e_coco_20220902_112414-78e30dcc.pth --device cpuWin下Pycharm运行/调试配置脚本形参执行主要改红色两处如果工作目录正确，脚本形参…...

编程日记 2025/6/1 17:05:18

Pytorch(无CPU搭建)+Jupyter

2024年最新最简洁深度学习环境配置：AnacondaPyTorch(CPU、GPU)VScodePycahrm_哔哩哔哩_bilibili 跟 PyCharm說再見, [VSCode] PythonJupyter 超牛逼的功能 ! 5分鐘大幅提升編碼效率~ 數據分析、AI大神必備_哔哩哔哩_bilibili...

编程日记 2025/5/22 4:56:40

类的高级特性与语法细节

static 静态关键字 Java中的static关键字用于修饰类的成员（属性或方法），表示“静态”的含义，即属于类本身，而非某个对象。静态成员在内存中只有一份，在类加载时初始化，生命周期贯穿程序运行始终…...

编程日记 2025/5/31 21:34:49

基于 RAG 的 Text2SQL 全过程的 Python 实现详解，结合 LangChain 框架实现自然语言到 SQL 的转换

什么是RAG 一、核心流程：三阶段协同 RAG的核心流程分为检索（Retrieval）、增强（Augmentation）、生成（Generation）三个阶段，形成“检索→知识整合→生成”的闭环。 1. 检索&#xff…...

编程日记 2025/6/1 10:29:35

使用 OpenCV 进行视觉图片调整的几种常见方法

以下是使用 OpenCV 进行视觉图片调整的几种常见方法： 调整图片大小指定目标尺寸：使用cv2.resize()函数，通过设定目标图像的宽度和高度来调整图片大小。例如，将图片调整为 200x200 像素： import cv2 image cv2.imre…...

编程日记 2025/5/31 4:29:03

【特殊场景应对9】视频简历的适用场景与风险分析

写在最前作为一个中古程序猿，我有很多自己想做的事情，比如埋头苦干手搓一个低代码数据库设计平台（目前只针对写java的朋友），比如很喜欢帮身边的朋友看看简历，讲讲面试技巧，毕竟工作这么多年，也做到过高管，有很多面人经历，意见还算有用，大家基本都能拿到想要的offe…...

编程日记 2025/6/3 8:24:01

Dify 1.3.0 为 LLM 节点引入了结构化输出支持

Dify 1.3.0 为 LLM 节点引入了结构化输出支持 0. 引言1. 使用方法 0. 引言 Dify 1.3.0 开始，在 LLM 节点支持结构化输出：Dify 已经为 LLM 节点引入了结构化输出支持。这意味着您的语言模型现在可以返回整齐组织且易于处理的数据。后端实现由 Nov1c444 在…...

编程日记 2025/6/4 10:51:24

【Linux网络】HTTP协议全解析 - 从请求响应到方法与Header

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/5/31 16:37:40

JSP实现用户登录注册系统（三天内自动登录）

JSP实现用户登录注册系统引言在Web开发中，用户认证是最基础且核心的功能之一。本文基于JSP技术，实现了一个包含注册、登录、自动登录（3天内）、退出等功能的用户系统，并在过程中解决了Cookie字符错误、错误信息回显…...

编程日记 2025/5/30 23:02:39

大数据模型现状分析

大数据模型现状分析一、引言在当今数字化时代，数据以前所未有的速度增长，大数据已成为推动各行业发展的核心动力。大数据模型作为挖掘数据价值的关键工具，正受到广泛关注与深入研究。通过对海量、多样且高速产生的数据进行处理和分析&…...

编程日记 2025/6/2 10:41:04

代码随想录算法训练营第二十八天

LeetCode题目: 509. 斐波那契数70. 爬楼梯746. 使用最小花费爬楼梯2444. 统计定界子数组的数目(每日一题) 其他: 今日总结往期打卡动态规划解题步骤: 确定递推公式确定遍历顺序记忆化搜索(确定dp数组以及下标的含义与初始化值)递推优化与空间优化 509. 斐波那契数跳转: 5…...

编程日记 2025/6/4 3:27:10

HTML与安全性：XSS、防御与最佳实践

HTML 与安全性：XSS、防御与最佳实践前言现代 Web 应用程序无处不在，而 HTML 作为其基础结构，承载着巨大的安全责任。跨站脚本攻击（XSS）仍然是 OWASP Top 10 安全威胁之一，对用户数据和网站完整性构成严…...

编程日记 2025/5/30 6:04:28

三维重建（二十）——思路整理与第一步的进行

文章目录一、整体思路二、细分三、之前存在问题四、任务安排五、第一步——找到内参并选定一种5.1 train的RTK5.2 test的RTK5.3 各选择一个5.3.1 train-185.3.2 test-193一、整体思路这部分主要是宏观的讲一下整体框架。从gshell里面提取核心参数，放入py3d，渲染出图片，…...

编程日记 2025/6/4 6:57:08

判断 ONNX 模型是否支持 GPU

🔍 判断 ONNX 模型是否支持 GPU 的几个关键点： ✅ 1. 检查模型支持的 Execution Provider 可以通过下面的代码打印出来当前模型使用了什么设备： 需要安装好：onnxruntime-gpu import onnxruntime as ort session ort.InferenceSe…...

编程日记 2025/5/29 7:06:07

CANFD技术在实时运动控制系统中的应用：协议解析、性能测试与未来发展趋势

摘要： 本文深入探讨了CANFD技术在实时运动控制系统中的应用。通过对传统CAN协议与CANFD协议的对比分析，详细阐述了CANFD在提升数据传输效率、增强系统实时性与稳定性方面的优势。文章结合具体测试案例，对CANFD总线的性能指标进行了全面评估&a…...

编程日记 2025/6/2 10:21:04

Java基础 4.26

1.访问修饰符细节 package com.logic.modifier;public class A {public int n1 100;protected int n2 200;int n3 300;private int n4 400;public void m1() {//在同一个类中可以访问public protected 默认 private 修饰属性和方法System.out.println(n1 " " …...

编程日记 2025/6/4 9:20:30

山东大学离散数学第九章习题解析

参考教材：离散数学教程，徐秋亮 / 栾俊峰 / 卢雷 / 王慧 / 赵合计编著，山东大学计算机科学与技术学院注：该解析为个人所写，涵盖了 2022-2023-2 学期赵合计老师所布置的所有课本习题；由于学识、认识及经验…...

编程日记 2025/6/2 5:33:39

5G融合消息PaaS项目深度解析 - Java架构师面试实战

5G融合消息PaaS项目深度解析 - Java架构师面试实战场景：互联网大厂Java求职者面试，面试官针对5G融合消息PaaS项目进行提问。第一轮提问面试官：马架构，请简要介绍5G融合消息PaaS平台的核心功能和应用场景。马架构&#xff…...

编程日记 2025/5/29 7:24:43

React-Redux

1、安装 npm i redux react-redux reduxjs/toolkit 2、基础使用方式（无 Toolkit） （1）核心Api createStore：创建数据仓库；store.dispatch()：用于派发action，执行修改动作&#xf…...

编程日记 2025/5/31 2:09:27

Linux基础篇、第4章_03系统磁盘高级管理LVM 逻辑卷管理器

题目：系统磁盘高级管理LVM 逻辑卷管理器版本号: 1.0,0 作者: 老王要学习日期: 2025.04.26 适用环境: Centos7 文档说明本文档聚焦于 Centos7 系统下的磁盘高级管理，围绕 LVM 逻辑卷管理器展开。详细介绍了物理卷、卷组和逻辑卷的创建、管理与删除操…...

编程日记 2025/6/3 4:32:51

代码随想录算法训练营Day36

力扣1049.最后一块石头的重量Ⅱ【medium】力扣474.一和零【meidum】一、力扣1049.最后一块石头的重量Ⅱ【medium】题目链接：力扣1049.最后一块石头的重量Ⅱ 视频链接：代码随想录 1、思路把这个问题转换成尽可能将 stones 分成两个等分子集&#xf…...

编程日记 2025/5/30 13:51:37

iperf网络性能测试

iperf 是一个网络性能测试工具，用于测量网络带宽、延迟、抖动等性能指标。它支持 TCP 和 UDP 协议，可以在客户端和服务器模式下运行，广泛用于网络性能评估和故障排查。主要功能带宽测试：测量网络的最大可用带宽。延迟测试&…...

编程日记 2025/5/31 8:23:30

基于 Nginx 的 WebSocket 反向代理实践

一、HTTP 协议升级机制回顾 Upgrade/Connection 报头客户端发起 WebSocket 握手时，会在普通 HTTP 请求中加入Upgrade: websocket Connection: Upgrade Sec-WebSocket-Key: <随机值> Sec-WebSocket-Version: 13服务端若接受协议切换，会以 101 Swit…...

编程日记 2025/5/30 21:33:12

C++ 同步原语

同步原语（Synchronization Primitives）是操作系统和编程语言提供的基本工具，用于在多线程或并发环境中协调线程（或进程）之间的执行顺序，管理共享资源的访问，以避免数据竞争（data rac…...

编程日记 2025/6/4 8:00:29

mmap详解

mmap详解 mmap基础概念mmap内存映射原理mmap相关函数调用mmap的使用细节mmap和常规文件操作的区别 mmap基础概念 mmap是一种内存映射文件的方法，即将一个文件或者其它对象映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一…...

编程日记 2025/6/1 12:38:45

基于大模型底座重构司法信息系统

前置篇章：法律智能体所需的基础知识构建一个高效的法律智能体，特别是在基于RAG（Retrieval-Augmented Generation）架构的背景下，需要融合多种学科和领域的知识。以下是对法律智能体开发和应用所需核心基础知识的简要介…...

编程日记 2025/5/30 22:21:48

如何判断你的PyTorch是GPU版还是CPU版？

如何判断你的PyTorch是GPU版还是CPU版？ PyTorch作为当前最流行的深度学习框架之一，支持在CPU和GPU(NVIDIA CUDA)上运行。对于深度学习开发者来说，正确识别PyTorch版本至关重要，因为GPU版本可以带来10-100倍的性能提升。本文将全面…...

编程日记 2025/5/30 21:00:48

输入格式

输出格式

输入输出样例

相关文章：