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

AcWing 299 裁剪序列

这道题算是我做过所有的单调队列优化 d p dp dp 题目中最难想的一道题,所以写篇题解再捋捋思路。


暴力

首先很容易想到设 d p i dp_i dpi 表示将前 i i i 个数划分成若干序列,【每个序列的最大值之和】的最小值。
那么就会有:
d p i = m i n { d p j + m a x k = j + 1 i { a k } } , 其中  0 ≤ j < i 且  ∑ k = j + 1 i a k ≤ m . dp_i = min \begin{Bmatrix} dp_j + max_{k = j + 1}^{i} \begin{Bmatrix} a_k \end{Bmatrix} \end{Bmatrix}, \\ 其中 \ 0 \leq j < i \ 且 \ \sum_{k = j + 1}^{i} a_k \leq m. dpi=min{dpj+maxk=j+1i{ak}},其中 0j<i  k=j+1iakm.
这样子的复杂度是 O ( n 3 ) O(n^3) O(n3),考虑优化。


优化

先证明一个东西,那就是 d p i dp_i dpi单调不减的(也就是非严格单调递增),即:对于任意的 i i i,都有 d p i ≤ d p i + 1 dp_i \leq dp_{i + 1} dpidpi+1
这是显然的,因为多加一个数,它如果单开一个序列,那么就会造成贡献;如果它归为最后一个已有的序列,那么若它比最后一序列中的最大值小,那么它就不会产生贡献,否则就会产生贡献,使最大值之和变大。

然后观察转移方程:
d p i = m i n { d p j + m a x k = j + 1 i { a k } } dp_i = min \begin{Bmatrix} dp_j + max_{k = j + 1}^{i} \begin{Bmatrix} a_k \end{Bmatrix} \end{Bmatrix} dpi=min{dpj+maxk=j+1i{ak}}
可以发现, m a x k = j + 1 i { a k } max_{k = j + 1}^{i} \begin{Bmatrix} a_k \end{Bmatrix} maxk=j+1i{ak} 随着 j j j 的增加,是非严格单调递减的,因为右端点 i i i 不动,所以 [ j + 1 , i ] [j + 1, i] [j+1,i] 中的的最大值是越来越小或者不变的。
因此我们就会有一个这样的发现:在 m a x k = j + 1 i { a k } max_{k = j + 1}^{i} \left \{ a_k \right\} maxk=j+1i{ak} 的值相等的情况下,我的决策点 j j j 是越靠前越好的(因为 d p i dp_i dpi单调不减的嘛)。
如此一来,在合法区间内有若干个的可能的最优决策点(分别对应使 m a x k = j + 1 i { a k } max_{k = j + 1}^{i} \left \{ a_k \right\} maxk=j+1i{ak} 值相等的最小的位置 j j j)。因此我们就用单调队列来维护 a k a_k ak 单调递减,队列所记录的位置就是一个可能的决策点。
至于查询所有可能决策点的最小贡献,用 m u l t i s e t multiset multiset 来实现(这句可能不好理解,可以先看代码)。

代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;int n, a[maxn];
ll m, s, dp[maxn];
int l[maxn];
int q[maxn], h, t;
multiset<ll> S;
int main() {scanf("%d%lld", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", a + i);if (a[i] > m) {printf("-1\n");return 0;}}// 预处理使 a[j+1...i] 之和小于等于 m 的最小 jfor (int i = 1, j = 0; i <= n; ++i) {s += a[i];while (s > m) s -= a[++j];l[i] = j;} h = 1, t = 0;for (int i = 1; i <= n; ++i) {// 如果之前的某些决策点已经不在合法区间// 那么就要删去, 其所对应的可能答案也要删去while (h <= t && q[h] < l[i]) {S.erase(dp[q[h]] + a[q[h + 1]]);++h;}// 维 a 护单调递减while (h <= t && a[q[t]] <= a[i]) {S.erase(dp[q[t - 1]] + a[q[t]]);--t;}if (h <= t) S.insert(dp[q[t]] + a[i]);q[++t] = i;// 这句是为了包括【队头的决策点】【从合法区间的最左端转移过来】的情况// 学校机房上传不了图片来解释,先鸽着dp[i] = dp[l[i]] + a[q[h]];  if (S.size()) dp[i] = min(dp[i], *(S.begin()));}printf("%lld\n", dp[n]);return 0;
}

相关文章:

AcWing 299 裁剪序列

这道题算是我做过所有的单调队列优化 d p dp dp 题目中最难想的一道题&#xff0c;所以写篇题解再捋捋思路。 暴力 首先很容易想到设 d p i dp_i dpi​ 表示将前 i i i 个数划分成若干序列&#xff0c;【每个序列的最大值之和】的最小值。 那么就会有&#xff1a; d p i …...

P2889 [USACO07NOV] Milking Time S

题目大意 有 N N N 个小时可以挤奶。其中有 m m m 个时间段可以给 Bessis 奶牛挤奶。第 i i i 个时间段为 s i s_i si​ ~ t i t_i ti​&#xff0c;可以获得 E f f i Eff_i Effi​ 滴奶。每次挤完奶后&#xff0c;人都要休息 R R R 小时。最后问&#xff0c;一共能挤出…...

基于Spring Boot的健康医院门诊在线挂号系统设与实现(LW+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

PyTorch-基础(CUDA、Dataset、transforms、卷积神经网络、VGG16)

PyTorch-基础 环境准备 CUDA Toolkit安装&#xff08;核显跳过此步骤&#xff09; CUDA Toolkit是NVIDIA的开发工具&#xff0c;里面提供了各种工具、如编译器、调试器和库 首先通过NVIDIA控制面板查看本机显卡驱动对应的CUDA版本&#xff0c;如何去下载对应版本的Toolkit工…...

复现论文:DPStyler: Dynamic PromptStyler for Source-Free Domain Generalization

论文&#xff1a;[2403.16697] DPStyler: Dynamic PromptStyler for Source-Free Domain Generalization github: TYLfromSEU/DPStyler: DPStyler: Dynamic PromptStyler for Source-Free Domain Generalization 论文: 这篇论文还是在PromptStyler:Prompt-driven Style Gener…...

6.将cr打包成网络服务|使用postman进行测试|编写oj_server的服务路由功能(C++)

将cr打包成网络服务 compile_server.cc #include "compile_run.hpp" #include "../comm/httplib.h"using namespace ns_compile_and_run; using namespace httplib;//编译服务随时可能被多个人请求&#xff0c;必须保证传递上来的code&#xff0c;形成源…...

基于SpringBoot + Vue的共享汽车(单车)管理系统设计与实现+毕业论文+开题报告+指导搭建视频

本系统包含管理员、用户两个角色。 管理员角色&#xff1a;个人中心管理、用户管理、投放地区管理、汽车信息管理、汽车投放管理、汽车入库管理、使用订单管理、汽车归还管理。 用户角色&#xff1a;注册登录、汽车使用下单、汽车归还。 本共享汽车管理系统有管理员和用户。管…...

Day54(补)【AI思考】-SOA,Web服务以及无状态分步解析与示例说明

文章目录 **SOA&#xff0c;Web服务以及无状态**分步解析与示例说明**分步解析与示例说明****1. 核心概念解析****2. 为什么说SOA与Web服务是“正交的”&#xff1f;****3. 架构风格 vs. 实现技术****4. 接口&#xff08;Interface&#xff09;的核心作用****5. Web服务的“被认…...

回溯算法之组合和排列问题

文章目录 1.什么是回溯算法2.回溯算法解题步骤3.回溯算法解决组合问题4.回溯算法解决排列问题 1.什么是回溯算法 回溯算法是一种通过尝试所有可能的解决方案来解决问题的算法策略&#xff0c;它通常用于求解组合优化、排列组合、路径搜索等类型的问题,是一种暴力求解的算法。 2…...

gihub上适合练手的Python项目

GitHub 上有许多适合练手的 Python 项目&#xff0c;涵盖了从初学者到中级开发者的不同难度级别。以下是一些推荐的项目类型和具体示例&#xff0c;帮助你提升 Python 编程技能&#xff1a; 1. 基础项目 适合初学者&#xff0c;帮助掌握 Python 基础语法和常用库。 示例项目&…...

解锁CSnakes:.NET与Python的融合魔法

一、引言 在软件开发的广袤领域中&#xff0c;我们常常面临各种复杂的业务需求和技术挑战。不同的编程语言犹如各具特色的工具&#xff0c;它们在不同的场景下展现出独特的优势。例如&#xff0c;C# 以其强大的类型系统和丰富的类库&#xff0c;在企业级应用开发中占据重要地位…...

Python常见面试题的详解16

1. 如何强行关闭客户端和服务器之间的连接&#xff1f; 在网络编程中&#xff0c;有时需要强行中断客户端和服务器之间的连接。对于基于 TCP 协议的连接&#xff0c;由于其面向连接的特性&#xff0c;需要采取特定的步骤来确保连接被正确关闭&#xff1b;而 UDP 是无连接协议&a…...

建筑兔零基础自学python记录29|实战词云可视化项目——分人物阵营词云(上)7

我们在上次情感分析的基础上&#xff0c;不分积极消极&#xff0c;按文本中人物的阵营分为3队。可以猜想按照积极消极分类是有现成的feeling可以分析&#xff0c;但人物阵营却是没有现成资料&#xff0c;需要额外给出信息的。 图1 图2 上面两图的文字大小和数量有区别&#xf…...

Vi 编辑器基本使用指南

一、Vi 编辑器的启动与退出 启动 Vi 编辑器 在终端中&#xff0c;输入vi加上要编辑的文件名&#xff0c;如vi example.txt&#xff0c;如果example.txt存在&#xff0c;Vi 编辑器会打开该文件&#xff1b;若不存在&#xff0c;则会创建一个新的空文件并打开。如果只输入vi&am…...

22、《Spring Boot消息队列:RabbitMQ延迟队列与死信队列深度解析》

Spring Boot消息队列实战&#xff1a;RabbitMQ延迟队列与死信队列深度解析 引言 在现代分布式系统中&#xff0c;消息队列承担着解耦、削峰填谷和异步通信的重要职责。本文将深入探讨Spring Boot与RabbitMQ的整合应用&#xff0c;重点解析延迟队列与死信队列的实现原理及实战…...

linux 命令+相关配置记录(持续更新...)

linux 命令记录相关配置记录 磁盘切换 cd D&#xff1a;#这里表示切换到D盘查看wsl 安装的linux 子系统 wsl --list -vwsl 卸载 linux 子系统 wsl --unregister -xxx # xxx 表示子系统的名字备份Linux 子系统 导出 wsl --export xxx yyy # xxx 表示子系统的名字 yyy 表示压…...

ssh工具

文章目录 ssh简介ssh远程连接Linux下使用SSH安装安装ssh服务端安装ssh客户端 命令启动重启查看ssh的状态 ssh 配置文件ssh连接地址 配置文件基本配置注意通配符心跳和密钥ssh的Include跳板 ProxyJump内网穿透 Windows下使用SSH安装ssh 配置文件ssh连接地址 配置文件 ssh简介 s…...

LLM大语言模型私有化部署-使用Dify的工作流编排打造专属AI诗词数据分析师

背景 前面的文章通过 Ollama 私有化部署了 Qwen2.5 (7B) 模型&#xff0c;然后使用 Docker Compose 一键部署了 Dify 社区版平台。 LLM大语言模型私有化部署-使用Dify与Qwen2.5打造专属知识库&#xff1a;在 Dify 平台上&#xff0c;通过普通编排的方式&#xff0c;创建了基于…...

Windows 图形显示驱动开发-WDDM 3.2-自动显示切换(二)

在 GPU0 和 GPU1 之间共享数据 在某些情况下&#xff0c;也许可以在某些时候带来更好的用户体验&#xff1a; GPU0 和 GPU1 来自同一个 IHV。GPU0 可以将操作系统无法解读的显示配置相关信息传递给 GPU1。 数据 Blob 由 GUID 描述&#xff0c;如果 GPU1 的驱动程序能理解数据…...

基于CentOS7安装kubesphere和Kubernetes并接入外部ES收集日志

一、修改所有节点主机名 主节点就修改成master hostnamectl set-hostname master 然后输入bash刷新当前主机名 工作节点1就修改成node1 hostnamectl set-hostname node1 然后输入bash刷新当前主机名 二、全部节点安装依赖并同步时间 yum -y install socat conntrack ebta…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...