关于斜率优化
  • 板块学术版
  • 楼主Kobe303
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/3/6 18:41
  • 上次更新2023/10/28 07:07:24
查看原帖
关于斜率优化
292300
Kobe303楼主2022/3/6 18:41

在《算法竞赛进阶指南》P323 中,有这样一段:

对上一题的解法二进行优化,先对状态转移方程稍作变形,把常数、仅与 ii 有关的项、仅与 jj 有关的项以及 i,ji,j 的乘积项分开。

Fi=min0j<i{Fj(S+sumTi)sumCj}F_i=\min\limits_{0\le j\lt i}\left\{F_j-(S+sumT_i)*sumC_j\right\}

          +sumTisumCi+SsumCN\ \ \ \ \ \ \ \ \ \ +sumT_i*sumC_i+S*sumC_N

min\min 函数去掉,把关于 jj 的值 FjF_jsumCjsumC_j 看作变量,其余部分看作常数,得到:

Fj=(S+sumTi)sumCjsumTisumCiSsumCNF_j=(S+sumT_i)*sumC_j-sumT_i*sumC_i-S*sumC_N

蒟蒻想问一个问题:为什么把 min\min 函数去掉能得到这个式子呢?

2022/3/6 18:41
加载中...