RainAir
My OI Blog
RainAir
斜率优化

题目链接

其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。

题目描述

你可以连续的输出一些单词,定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。

其中 $ N \leq 500000,M \leq 1000 $

解题报告

这是一道基本的斜率优化的题目。

动态规划的式子我们都很好推,设 $ f_i $ 表示输出前 $i$ 个单词的最小代价,有转移方程

$$ f_i = min{f_j + (S_j-S_i)^2 + M} $$

其中 $1 \leq j < i$,$ S$ 表示 $a$ 的前缀和。

但这个朴素的 dp 是 $O(n^2)$,会超时。我们要想办法 $O(1)$ 找出 $ min( f_j + (S_j-S_i)^2 + M ) $。

于是我们不妨设在这个转移求 $f_i$ 的过程中,从 $j$ 转移要比从 $k$ 转移要更优 $(j < k)$ 。如此可以得到:

$ f_j + (S_j – S_i)^2 + M < f_k + (S_k-S_i) + M \tag 1$

进行一系列的小学数学化简,得到

(为了简便这里的 $S_i$ 表示 $1$ 到 $i-1$ 的和)

$$ \frac{f_j-f_k+S_j^2-S_k^2}{S_j-S_k} < 2S_{i+1} \tag2$$

我们不妨设 $ F_i = f_i + S_i\ ^2 $,那么式子可以表示为:

$$ \frac{F_j – F_k}{S_j – S_k} < 2S_{i+1}\tag3$$

即当且仅当 $ (j < k) $ 且 $$ \frac{F_j – F_k}{S_j – S_k} < 2S_{i+1} $$ 成立的时候,从 $j$ 转移才更优。

然后我们发现这个式子…很像斜率。我们对于每一个确定的状态对应到空间中每一个点 $ (S_i,F_i) $。

进行转移的时候,考虑在一条直线上的两个点,他们的斜率关系能直接反应是否从这里转移。

所以说我们就维护一个下凸壳,每次更新出状态的时候加入这个点并维护凸壳,但还是不能 $O(1)​$ 求。

其实最后我们发现这个函数是单调的,可以用单调队列维护,达到了 $O(1) $ 找出转移状态的目的。

时间复杂度最后为 $O(n)$

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/68
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

斜率优化
题目链接 其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。 题目描述 你可以连续的输出一些单词,定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j …
扫描二维码继续阅读
2018-09-03
标签
近期评论