%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96%E4%B8%8EWQS%E5%B8%A6%E6%9D%83%E4%BA%8C%E5%88%86%E4%BC%98%E5%8C%96DP

[giscus[bot]]

%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96%E4%B8%8EWQS%E5%B8%A6%E6%9D%83%E4%BA%8C%E5%88%86%E4%BC%98%E5%8C%96DP

1.前言 本文章图较多！ 动态规划在转移的时候，我们称最终转移过来的状态为决策点。 而对于斜率优化和WQS带权二分都是利用凸包和切线的概念来优化DP 2.凸包与切线 2.1 凸包 凸包是什么呢？其实就是字面意思，一个凸起的小包，但是这个是描述图形的。如下图： 严谨来说，应当是其图形的切线斜率是具有单调性，其导函数f′(x)f'(x)f′(x)具有单调性。 但是在OI中一般凸包都不

https://worldcpu.github.io/%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96%E4%B8%8EWQS%E5%B8%A6%E6%9D%83%E4%BA%8C%E5%88%86%E4%BC%98%E5%8C%96DP.html

[Worldcpu]

123456