斜率优化DP_股市动态_中意财经网

斜率优化DP

创始人

2025-05-29 16:09:06

0次

一.考虑如下DP方程

1.m为常数，s表示数组前缀和

$dp[i]=min(dp[j]+(s[j]-s[i]])^2)+m$

2.化简可得 $dp[i]=dp[j]+s[j]^2+s[i]^2-2s[i]s[j]+m$

3.观察式子可知，若想dp[i]更小,则需要 $dp[j]+s[j]*s[j]$ 更小

4.因此dp方程转换为 $dp[j]=s[j]^2=dp[i]-s[i]^2+2s[i]s[j]+m$

5.令y等于 $dp[j]+s[j]^2$ ，k等于 $2s[i]$ ，x等于 $dp[i]+s[i]^2+m$

6.又因为 $s[i]$ 递增，因此用一个单调队列维护凸包即可

二.出队优化

1.队首出队

若存在两个点a,b,且a

若i从b转移优于从a转移，则有 $dp[b]+(s[i]-s[b]^2)+m<=dp[a]+(s[i]-s[a])^2+m$

化简式子后 $(dp[b]+s[b]^2)-(dp[a]+s[a]^2)<=2s[i](s[b]-s[a])$

又因为 $s[b]-s[a]>0$ ,因此移项可得

$\frac{((dp[b]+s[b]^2)-(dp[a]+s[a]^2))}{(s[b]-s[a])}<=2s[i]$ 时从队首弹出

2.队尾出队

考虑下方情况，因为斜率递增，因此答案取t1一定不优

因此要去掉t1,如果t1和t2斜率大于t1和i的斜率那么t1出队

$Yt1=dp[t1]+s[t1]^2\;\;\;\;Xt1=s[t1]$

$Yt2=dp[t2]+s[t2]^2\;\;\;\;Xt2=s[t2]$

$Yi = dp[i]+s[i]^2\;\;\;\;Xi=s[i]$

则 $k1=\frac{(Yt1-Yt2)}{(Xt1-Xt2)}\;\;\;\;\;k2=\frac{(Yi-Yt1)}{(Xi-Xt1)}$

若k1>=k2，则弹出t1，式子化简为

$(Yt1-Yt2)*(Xi-Xt1)>=(Yi-Yt1)*(Xt1-Xt2)$

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：许家印、中国恒大再被签发限消令！许家印恒大被限消许家印被限消

下一篇：广东省投教基地“成绩单”出炉：两家升级，两家降级广东省投教基地“成绩单”出炉：两家升级，两家降级

相关内容

热门资讯

我们该如何看待此次“青岛代理人... 这是一起典型的利用职业身份作掩护的个人涉嫌诈骗犯罪案件。文/每日财报栗佳近日，泰康人寿青岛分公司...

62岁李福春续任董事长！东北证... 本文来源：时代周报作者：李茜楠、卢泳志图源：图虫创意5月15日，东北证券（000686.SZ）公告...

商务部新闻发言人就中美经贸磋商... 据商务部网站消息，商务部新闻发言人就中美经贸磋商初步成果答记者问，全文如下：问：5月14日，中美两国...

下周财经日历（5月18日-5月...

原创花... 长沙晚报掌上长沙5月15日讯（全媒体记者张洋子）只要花钱，就能“洗白”逾期记录、“修复”不良征信？...

芯片初创公司Taalas融资1... 2月23日消息，总部位于多伦多的芯片初创企业Taalas近日宣布，已完成1.69亿美元融资，并表示已...

原创特... 特朗普打心底认可中国实力，他认为世界上只有两个超级大国，一个是美国，另一个是中国，俄罗斯在他眼里已经...

下周（2月23日-3月1日）市... 2月22日消息，下周（2月23日-3月1日）市场大事预告：1. 中国2月LPR将于2月24日出炉，预...

65天接待306万游客，第二十... 2月22日消息，第二十七届哈尔滨冰雪大世界昨日正式闭园。从2025年12月17日开园以来，园区运营6...

应急管理部：要全力抓好节后返程... 2月22日消息，今天下午，应急管理部召开春节假期视频调度会，分析当前安全形势，调度部署烟花爆竹等重点...