Peter算法小课堂—动态规划斜率优化

2024-04-12 23:52

本文主要是介绍Peter算法小课堂—动态规划斜率优化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大家来到这一堂课,就说明大家已经学过函数了

直线方程:y=kx+b

大家可以算一算。

其实,在数学上,这玩意要分类讨论

那么,这唯一的交点就是我们要背出来的

直线最值

这像一个分段函数

其实,只有部分直线能提供最小值,另外的,就可以省略

当然,最大值也一样。

看一下太戈编程第2627题

题目

在平面直角坐标系里,横坐标为x,纵坐标为y。有n条直线,第i条直线的形式为:y=b[i]+k[i]*x。其中整数b[i]为截距,整数k[i]为斜率。已知k[i]随着i的增加而减小。另外有m个从小到大排布的横坐标,第i个为x[i]。请求出在每个横坐标位置上各个直线的纵坐标最小值是多少?(纯数学)

暴力

struct Line{ll b,k;} lines[N];
int main(){ll n,m;cin>>n>>m;for(ll i=1;i<=n;i++) cin>>lines[i].b;for(ll i=1;i<=n;i++) cin>>lines[i].k;for(ll i=1;i<=m;i++) cin>>x[i];for(ll i=1;i<=m;i++){ans[i]=INF;for(ll j=1;j<=n;j++){ans[i]=min(ans[i],lines[j].b+lines[j].k*x[i]);}}for(int i=1;i<=m;i++) cout<<ans[i]<<" ";return 0;
}

时间复杂度不太行

优化

根据前面的分析,

但是,这好像只能做到常数级别的优化

注意:斜率递减

2号和0号的节点在2号和1号节点左侧,那么说明,1号线是废线,可以省略。

做之前,要做准备工作

struct Line{ll b,k;} lines[N];
ld X(ll u,ll v){return -(ld)(lines[u].b-lines[v].b)/(lines[u].k-lines[v].k);
}

然后,我们维护一个队列,里面是可能参与最小值的直线编号

ll l=1,r=1;
for(ll i=1;i<=n;++i){while(r-l>=2&&X(i,q[r-1])<X(q[r-1],q[r-2])) r--;q[r++]=i;
}

筛完了,剩下一个上凸轮廓。那么,一条直线只会提供一部分最小,之后的我们称之为“过气的直线”

假设现在有两条直线l,l+1,程序运行到x[i]。当x[i]在交点右侧时,l+1提供最小;当x[i]在交点左侧时,l+1不能提供最小。

for(ll i=1;i<=m;++i){while(r-l>=2&&X(q[l],q[l+1])<x[i]) ++l;int j=q[l];ans[i]=lines[j].b+lines[j].k*x[i];
}

书籍叠放1

题目

你有n本书,编号1到n,需要分几堆叠放在桌面上。每本书的正面都是一个长方形,共四条边,左右两侧边长对应长方形的长度,上下两侧边长对应长方形的宽度。第i本书的长度为h[i],宽度为w[i]。你可以选择任意几本书分出任意的堆数。但是,叠放的时候要注意,每本书两两之间都保持上下左右四条边平行,不能旋转。每组叠放好的书都会在桌面上占据一定的面积。例如我们将3本书叠放在一堆里:第一本长度为1宽度为4,第二本长度为2宽度为3,第三本长度为3宽度为2,这三本占据的面积为长度为3宽度为4的长方形面积,也就是3*4=12。

目前,已知你的书籍满足一种特殊顺序:你发现随着编号i增加,书的长度h[i]增加,宽度w[i]减少。请问,经过合理叠放后,总体占据的面积最小是多少?

这是一道dp题,可以用朴素

朴素

cin>>n;
for(ll i=1;i<=n;i++) cin>>bk[i].h>bk[i].w;
for(ll i=1;i<=n;++i){f[i]=bk[1].w*bk[i]*h;for(ll j=1;j<i;++j)f[i]=min(f[i],f[j]+bk[j+1].w*bk[i].h);
}

优化

这个看起来像直线最值吗

解释完毕

索道选址II

题目描述

lester的老家有一个著名的旅游景点:大牛山。据说爬完就能成为C++大牛,所以游客不断。从山脚到山顶共有n个景点,排成一条直线。山顶为景点n,并且只有这一条登山路线orz。由于山太高,当地政府决定架设若干条索道站点。索道站点山上某个景点,并且到山顶(景点n)是必须有索道站点的。在景点i修建索道站点的花费为Ai。对于没有索道直达的景点,游客会乘坐高于该景点且最近的一个索道站点,然后从该站点向下走到目的地。步行游客会产生一定的不满意度,值等于索道站点与目的地编号之差。你可以认为想去每个景点的游客人数是相同的,例如索道站点在景点3,6,则去景点4需要先到景点6,然后向下走到景点4,不满意度为6-4=2。lester既不想花太多钱,又不愿意积累太多的不满意度。注意:游客出发的位置可以理解为在0号,而不是1号。他希望求一种折衷方案,使得花费与不满意度总和最小。

f[i]表示用前i个选址覆盖前i个景点最小代价,且上一段为j。则不满意度为

也就是j+1加到i-1。

最后,我们以-j为斜率,f[j]+1/2*(j+1)*j为截距画直线

这篇关于Peter算法小课堂—动态规划斜率优化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/898586

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语