斜率优化学习笔记

浅谈数形结合思想在信息学竞赛中的应用

参考博客

这个东西英文好像叫做:convex hull trick

Convex_hull_trick_wiki
codeforces convex hull trick

 

简单说说我的理解:斜率优化是一种数形结合的思想。。。

对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。

简单地说。。。如果把状态的下标和状态对应成二维平面的点。。。

凸起来的点一定不会影响答案。。。

具体证明参考论文。。。。。

也就是维护一个”下凸折线”

具体维护的办法是用单调队列来维护。。。

感觉还是挺简单的。。。。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz