浅谈关于斜率优化中为什么能转换为横截式

本文介绍了动态规划中的一种优化技巧——凸包优化。通过分析dp状态转移方程,利用几何直观理解最优子结构的选择原则,并结合凸包来维护当前最优解。文中详细解释了如何将复杂的转移方程简化为易于求解的形式。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

通常的dp转移为现在处理到的dp[i],要在前面的dp状态中找到一个最优的状态dp[k]转移过来。
设转移方程为dp[i]=max{dp[i],a[i]*x[k]+b[i]*y[k]}
相当于在二维坐标系中有很多点,要选取最优的点,产生最优的价值。
样例
而几乎每个点的X坐标和Y坐标都不相同,怎么比较最优?
相信大部分人都已经猜到了。
X和Y是存在转换比例的,且X转换到Y的比例就是a[i]/b[i],也就是图中的斜线的斜率。
那一条直线上的点都是等优的。
然后为什么是横截式就很简单了,就是将X全部转换成Y,就很容易看出最优了。
即我们要最大化直线方程Y(j)=-A[i]/B[i]*X(j)+dp[i]/B[i]的截距。
弄个凸包维护就行了,有单调性的话就用单调队列。
脑子热~~

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值