斜率优化DP – Solutions

斜率优化是将方程看起来非常可推的dp从\( O(n^2) \)优化至\( O(n) \)的优秀方法,这种优化是基于决策单调性的……………………

一句话:都是套路。

关于斜率优化的文章很多,而且我数学贼差QAQ(主要是懒),就直接指向一篇本校神犇HenryPigLi的斜率优化DP,虽然他推得有点乱但是还算能看。
然而他的文章还有一个好,就是底下给的题比其他blog都多,于是我觉得应该把solution发出来。 (更多…)








ˆ Back To Top