当前位置: 首页 > 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…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...